实现手指树时出现类型错误
Type error when implementing finger trees
我想按照 Hinze (see also this blog 的 (Haskell) 论文中的描述使用 2-3 个手指树。
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 函数工作，它抱怨类型不匹配：
Expecting a FingerTree<'a> but given 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 中遇到过这个错误，但能够通过在函数上添加完整的类型信息来解决它。
// 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这似乎还不够，所以我也尝试在函数中间添加类型（看评论）。没用。
我有点理解错误及其来源。谁能告诉我如何让它工作？恕我直言，这应该是可能的，否则 prepend 也不会编译。也许像 this 这样的技巧有帮助？ （虽然看不懂）
PS: 我也把代码放在FsSnip上，在浏览器里玩玩。
viewl 或 prepend 等函数依赖于 polymorphic recursion：对 prepend 的递归调用采用与原始调用不同类型的参数。您可以在 F# 中定义此类函数，但正如您发现的那样，它们需要 full 类型注释（否则您会收到非常混乱的错误消息）。特别要注意的是，类型参数在函数的定义中必须是显式的（尽管它们通常可以在调用点推断出来）。所以第一个问题就是需要在定义中指定viewl<'a>
然而，还有一个非常微妙的第二个问题，它与 Digit<_>.OfList 有关。尝试将第一个代码块发送到 F# interactive 并查看生成的定义的签名：您将看到 static member OfList : (obj list -> Digit<obj>)，这将导致 viewl 无法正确定义。所以发生了什么事？您还没有给 OfList 一个签名，所以它不会是一个泛型方法（函数将被泛化，但成员永远不会）。但是编译器也无法推断出您打算将输入列表设为 'a list 类型，其中 'a 是类型的通用参数 - 为什么它会推断出此特定类型而不是 int list 或 string list 等？所以它选择了一个无聊的单态默认值（obj list），除非你在后续代码中做一些事情来将它限制为不同的具体单态类型。相反，你需要在 Digit 上添加签名，然后一切都会好起来的。
通常在 F# 中，为每个类型创建一个单独的模块来定义相关函数（如 ToList 等）是惯用的。由于函数定义是通用的，这也可以避免 Digit 问题你面对这里。也就是说，您可以像这样构建代码：
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!"
我想按照 Hinze (see also this blog 的 (Haskell) 论文中的描述使用 2-3 个手指树。
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 函数工作，它抱怨类型不匹配：
Expecting a FingerTree<'a> but given 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 中遇到过这个错误，但能够通过在函数上添加完整的类型信息来解决它。
// 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这似乎还不够，所以我也尝试在函数中间添加类型（看评论）。没用。
我有点理解错误及其来源。谁能告诉我如何让它工作？恕我直言，这应该是可能的，否则 prepend 也不会编译。也许像 this 这样的技巧有帮助？ （虽然看不懂）
PS: 我也把代码放在FsSnip上，在浏览器里玩玩。
viewl 或 prepend 等函数依赖于 polymorphic recursion：对 prepend 的递归调用采用与原始调用不同类型的参数。您可以在 F# 中定义此类函数，但正如您发现的那样，它们需要 full 类型注释（否则您会收到非常混乱的错误消息）。特别要注意的是，类型参数在函数的定义中必须是显式的（尽管它们通常可以在调用点推断出来）。所以第一个问题就是需要在定义中指定viewl<'a>
然而，还有一个非常微妙的第二个问题，它与 Digit<_>.OfList 有关。尝试将第一个代码块发送到 F# interactive 并查看生成的定义的签名：您将看到 static member OfList : (obj list -> Digit<obj>)，这将导致 viewl 无法正确定义。所以发生了什么事？您还没有给 OfList 一个签名，所以它不会是一个泛型方法（函数将被泛化，但成员永远不会）。但是编译器也无法推断出您打算将输入列表设为 'a list 类型，其中 'a 是类型的通用参数 - 为什么它会推断出此特定类型而不是 int list 或 string list 等？所以它选择了一个无聊的单态默认值（obj list），除非你在后续代码中做一些事情来将它限制为不同的具体单态类型。相反，你需要在 Digit 上添加签名，然后一切都会好起来的。
通常在 F# 中，为每个类型创建一个单独的模块来定义相关函数（如 ToList 等）是惯用的。由于函数定义是通用的，这也可以避免 Digit 问题你面对这里。也就是说，您可以像这样构建代码：
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!"