实施手指树时出现类型错误 [英] Type error when implementing finger trees
问题描述
我想按照博客).
I wanted to play around with 2-3 finger trees as described in the (Haskell) paper by Hinze (see also this blog).
type Node<'a> =
| Node2 of 'a * 'a
| Node3 of 'a * 'a * 'a
static member OfList = function
| [a; b] -> Node2(a, b)
| [a; b; c] -> Node3(a, b, c)
| _ -> failwith "Only lists of length 2 or 3 accepted!"
member me.ToList () =
match me with
| Node2(a, b) -> [a; b]
| Node3(a, b, c) -> [a; b; c]
type Digit<'a> =
| One of 'a
| Two of 'a * 'a
| Three of 'a * 'a * 'a
| Four of 'a * 'a * 'a * 'a
static member OfList = function
| [a] -> One(a)
| [a; b] -> Two(a, b)
| [a; b; c] -> Three(a, b, c)
| [a; b; c; d] -> Four(a, b, c, d)
| _ -> failwith "Only lists of length 1 to 4 accepted!"
member me.ToList () =
match me with
| One a -> [a]
| Two(a, b) -> [a; b]
| Three(a, b, c) -> [a; b; c]
| Four(a, b, c, d) -> [a; b; c; d]
member me.Append x =
match me with
| One a -> Two(a, x)
| Two(a, b) -> Three(a, b, x)
| Three(a, b, c) -> Four(a, b, c, x)
| _ -> failwith "Cannot prepend to Digit.Four!"
member me.Prepend x =
match me with
| One a -> Two(x, a)
| Two(a, b) -> Three(x, a, b)
| Three(a, b, c) -> Four(x, a, b, c)
| _ -> failwith "Cannot prepend to Digit.Four!"
[<NoComparison>]
[<NoEquality>]
type FingerTree<'a> =
| Empty
| Single of 'a
| Deep of Digit<'a> * FingerTree<Node<'a>> * Digit<'a>
type Digit<'a> with
member me.Promote () =
match me with
| One a -> Single a
| Two(a, b) -> Deep(One a, Empty, One b)
| Three(a, b, c) -> Deep(One a, Empty, Two(b, c))
| Four(a, b, c, d) -> Deep(Two(a, b), Empty, Two(c, d))
type View<'a> = Nil | View of 'a * FingerTree<'a>
现在，我只是无法使viewl函数正常工作，它抱怨类型不匹配:
Now I just cannot get the viewl function working, it complains about a type mismatch:
期待一个FingerTree<'a>，但给出一个FingerTree>.
Expecting a FingerTree<'a> but given a FingerTree>.
当统一"a"和"Node<'a>" FingerTree时，结果类型将是无限的.
The resulting type would be infinite when unifying ''a' and 'Node<'a>' FingerTree.
let rec viewl : FingerTree<'a> -> View<'a> = function
| Empty -> Nil
| Single x -> View(x, Empty)
| Deep(One x, deeper(*:FingerTree<'a>/FingerTree<Node<'a>>*), suffix) ->
let rest =
match viewl deeper with
| Nil ->
suffix.Promote()
| View (node(*:Node<'a>*), rest) ->
let prefix = node.ToList() |> Digit<_>.OfList
Deep(prefix, rest, suffix)
View(x, rest)
| Deep(prefix, deeper, suffix) ->
match prefix.ToList() with
| x::xs ->
View(x, Deep(Digit<_>.OfList xs, deeper, suffix))
| _ -> failwith "Impossible!"
我以前在prepend中遇到此错误，但是能够通过在函数中添加完整类型信息来解决该错误.
I had this error before in prepend but was able to resolve it by adding the full type info on the function.
// These three/four type annotations solved the problem.
let rec prepend<'a> (a:'a) : FingerTree<'a> -> FingerTree<'a> = function
| Empty -> Single a
| Single b -> Deep(One a, Empty, One b)
| Deep(Four(b, c, d, e), deeper, suffix) ->
Deep(Two(a, b), prepend (Node3(c, d, e)) deeper, suffix)
| Deep(prefix, deeper, suffix) ->
Deep(prefix.Prepend a, deeper, suffix)
对于viewl，这似乎还不够，因此我也尝试在函数的中间添加类型(查找注释).没用.
For viewl this doesn't seem to be enough, so I also tried adding types in the middle of the function (look for the comments). It didn't work.
我有点理解错误以及错误的出处.谁能告诉我如何使它工作?恕我直言，这应该是可能的，因为否则prepend也不会编译.也许像此这样的技巧有帮助吗? (虽然不明白).
I kind of understand the error and where it is coming from. Can anyone tell me how to get this working? IMHO, it should be possible, because otherwise prepend would also not compile. Maybe a trick like this helps? (Don't understand it though).
PS:我还将代码放在 FsSnip 上，以便在浏览器中播放.
PS: I also put the code on FsSnip for playing around in the browser.
推荐答案
Functions like viewl or prepend rely on polymorphic recursion: the recursive call to prepend takes an argument of a different type than the original call. You can define such functions in F#, but as you discovered they require full type annotations (or else you get a very confusing error message). In particular, note that the type parameters must be explicit in the function's definition (though they can typically be inferred at call sites). So the first problem is that you need to specify viewl<'a> in the definition.
但是，还有一个非常细微的第二个问题，涉及到Digit<_>.OfList.尝试将第一部分代码发送到F#交互式代码，并查看结果定义的签名:您将看到static member OfList : (obj list -> Digit<obj>)，随后将使它变得无法正确定义viewl.所以发生了什么事?您尚未为OfList提供签名，因此它不是通用方法(函数将被泛化，但成员将不会被泛化).但是编译器也无法推断出您打算让输入列表的类型为'a list，其中'a是该类型的通用参数-为什么要推断此特定类型而不是int list或string list，等等.?因此，它选择了无聊的单态默认值(obj list)，除非您在后续代码中进行了一些操作以将其限制为其他具体的单态类型.相反，您需要向Digit添加签名，然后一切都会好起来.
However, there's an extremely subtle second problem, which concerns Digit<_>.OfList. Try sending the first chunk of code to F# interactive and looking at the signatures of the resulting definitions: you'll see static member OfList : (obj list -> Digit<obj>), which will subsequently make it so that viewl can't be defined correctly. So what happened? You haven't given a signature to OfList, so it won't be a generic method (functions will be generalized, but members never will be). But the compiler also can't infer that you intended for the input list to be of type 'a list where the 'a is the type's generic parameter - why would it infer this specific type rather than int list or string list, etc.? So it chooses a boring monomorphic default (obj list), unless you do something in subsequent code to constrain it to a different concrete monomorphic type. Instead, you need to add a signature to Digit and then everything will be fine.
在F#中，通常会为每种类型创建一个单独的模块来定义诸如ToList之类的相关功能，这是惯用的.由于功能定义是通用的，因此还可以避免您在此处遇到的Digit问题.也就是说，您可以像这样构建代码:
Often in F# it is idiomatic to create a separate module per-type to define related functions like ToList, etc. Since function definitions are generalized, this would also have avoided the Digit problem you face here. That is, you could structure your code like this:
type Node<'a> =
| Node2 of 'a * 'a
| Node3 of 'a * 'a * 'a
module Node =
let ofList = function
| [a; b] -> Node2(a, b)
| [a; b; c] -> Node3(a, b, c)
| _ -> failwith "Only lists of length 2 or 3 accepted!"
let toList = function
| Node2(a, b) -> [a; b]
| Node3(a, b, c) -> [a; b; c]
type Digit<'a> =
| One of 'a
| Two of 'a * 'a
| Three of 'a * 'a * 'a
| Four of 'a * 'a * 'a * 'a
[<NoComparison>]
[<NoEquality>]
type FingerTree<'a> =
| Empty
| Single of 'a
| Deep of Digit<'a> * FingerTree<Node<'a>> * Digit<'a>
module Digit =
let ofList = function
| [a] -> One(a)
| [a; b] -> Two(a, b)
| [a; b; c] -> Three(a, b, c)
| [a; b; c; d] -> Four(a, b, c, d)
| _ -> failwith "Only lists of length 1 to 4 accepted!"
let toList = function
| One a -> [a]
| Two(a, b) -> [a; b]
| Three(a, b, c) -> [a; b; c]
| Four(a, b, c, d) -> [a; b; c; d]
let append x = function
| One a -> Two(a, x)
| Two(a, b) -> Three(a, b, x)
| Three(a, b, c) -> Four(a, b, c, x)
| _ -> failwith "Cannot prepend to Digit.Four!"
let prepend x = function
| One a -> Two(x, a)
| Two(a, b) -> Three(x, a, b)
| Three(a, b, c) -> Four(x, a, b, c)
| _ -> failwith "Cannot prepend to Digit.Four!"
let promote = function
| One a -> Single a
| Two(a, b) -> Deep(One a, Empty, One b)
| Three(a, b, c) -> Deep(One a, Empty, Two(b, c))
| Four(a, b, c, d) -> Deep(Two(a, b), Empty, Two(c, d))
type View<'a> = Nil | View of 'a * FingerTree<'a>
let rec viewl<'a> : FingerTree<'a> -> View<'a> = function
| Empty -> Nil
| Single x -> View(x, Empty)
| Deep(One x, deeper, suffix) ->
let rest =
match viewl deeper with
| Nil -> suffix |> Digit.promote
| View (node, rest) ->
let prefix = node |> Node.toList |> Digit.ofList
Deep(prefix, rest, suffix)
View(x, rest)
| Deep(prefix, deeper, suffix) ->
match prefix |> Digit.toList with
| x::xs ->
View(x, Deep(Digit.ofList xs, deeper, suffix))
| _ -> failwith "Impossible!"
这篇关于实施手指树时出现类型错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
