Type error when using finger trees

Question

I wanted to play with 2-3 finger trees, as described in the (Haskell) Hinze document (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> 

Now I just can't get the viewl function viewl work, it complains about a type mismatch:

Waiting for FingerTree <'a>, but considering FingerTree>.

The resulting type would be infinite when combining '' 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!" 

I had this error before in prepend , but I was able to resolve it by adding full information about 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) 

For viewl this doesn't seem to be enough, so I also tried adding types in the middle of the function (look for comments). This did not work.

I understand the error and where it comes from. Can someone tell me how to do this? IMHO, this should be possible, because otherwise the prepend also not compile. Maybe a trick like this helps? (I don’t understand, though).

---

PS: I also put the FsSnip code to play in the browser.

Answer 1

Functions such as viewl or prepend rely on polymorphic recursion : a 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 have discovered, they need full annotations (or you will get a very confusing error message). In particular, note that type parameters must be explicit in the function definition (although they can usually be displayed on call sites). So the first problem is that you need to specify viewl<'a> in the definition.

However, there is a very subtle second issue that concerns Digit<_>.OfList . Try sending the first code snippet to F # interactive and look at the signatures of the resulting definitions: you will see a static member OfList : (obj list -> Digit<obj>) , which subsequently makes the viewl unable to determine correctly. So what happened? You did not give a signature for OfList , so this will not be a common method (functions will be generalized, but members will never be). But the compiler also cannot conclude that you have chosen the type of the input list of type 'a list , where 'a is a type parameter of the type - why it should output this particular type and not int list or string list , etc. ? Therefore, he chooses a boring monomorphic default value ( obj list ), unless you do something in the following code to restrict it to another specific monomorphic type. Instead, you need to add a signature to Digit , and then everything will be fine.

Often in F # it is idiomatic to create a separate module for each type to define related functions such as ToList , etc. Since the definitions of functions are generalized, this would also avoid the problem with Digit that you encounter here. That is, you can structure your code as follows:

 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!"