Back to Questions
1.0k
views7
comments
Why does type inference fail here?
f#compiler
1
2
3
4
5
6
7
8

type fastnum = int list

let fastnum_tostring (num:fastnum) = 
    let builder = new StringBuilder()
    let append digit (builder:StringBuilder) = 
        builder.Append(digit)
    List.fold_right append num builder |> ignore
    builder.ToString()

The idea here is to represent an integer as a list of digits, so that I can quickly play around with individual digits. This code gives an error saying that the method Append is overloaded, and it cannot deduce the type of digit. However, num is declared to be an int list, and append is a function with local scope and hence cannot be used anywhere outside of the implementation of fastnum_tostring. Inside the implementation of fastnum_tostring, the only place append is used is inside a call to List.fold_right, whose signature (the function) is declared to be of type ('a -> 'state -> 'state) -> 'a list -> 'state -> 'state. Since the second argument is of type 'a list, which I pass the value num, which is of type int list, why can't the compiler deduce that 'a = int?

.

Hi,
the F# type-inference algorithm is left-to-right only, which means that when it infers the type of "append" function it doesn't yet know that the type of "digit" will be an integer. This means that it really sees just this function:

1
2
3

 
let append digit (builder:StringBuilder) = 
        builder.Append(digit)

And from this, it can't tell which of the "Append" overloads to use. If you don't want to write type annotations here, you can also use "string" function that converts anything to string - "append" will then work with any type:

1
2

 
builder.Append(string digit)

But I would just use type annotation... You need them more frequently when working with .NET types.

By on 11/18/2008 7:16 AM ()

Is there any way to declare append as a lambda function and perhaps using the pipelining operator |> instead of an explicitly named function 'append' such that it would be able to deduce the type of digit? This way it could in theory see that an int list is going to be passed to the function before it sees the actual function. Not necessarily for practical purposes, but just so that I can get a better understanding.

By on 11/18/2008 7:25 AM ()

Glad you asked; this is the first time I have ever tried using the ||> operator in practice:

1
2
3
4
5

open System.Text
let fastnum_tostring (num:int list) = 
    let builder = new StringBuilder()
    (num, builder) ||> List.fold_right (fun digit builder -> builder.Append(digit)) |> ignore
    builder.ToString()

||> is like |> except it takes a 2-tuple on the left and passes both parts as arguments to the right; we need it here since two arguments come after the lambda in the "List.fold_right (fun...)" call.

By on 11/18/2008 7:40 AM ()

Hah! Well, glad you answered because another question that has been lingering on the back of my mind for quite some time now is "why is the |> operator limited to only being able to pass the rightmost argument?" I wasn't even aware of the ||> operator. I don't have an F# compiler handy on the computer I'm on now, but is there a |||> operator for a 3-tuple, or does it stop at 2? Is there a technical limitation that prevents the designers from allowing a generic pipeline operator that takes an arbitrarily-sized tuple and passes the arguments one by one?

By on 11/18/2008 10:22 AM ()

The type is different in each case (each arity tuple has a different type).

The definition of |> is just

1
2
3

let (|>) x f = f x

// also try let g x f = x |> f and hover over g in VS

You may find it instructive to try to author ||> and |||> yourself (the library only has versions up to 3, which I expect will be as many as you'll ever find useful in practice) and inspect the types, to understand this better.

By on 11/18/2008 1:44 PM ()

Hmm, yea it seems there's no way to recursively process elements of a tuple in sequence. I thought that, given an arbitrary n-ary tuple, you could split it into the first element, and then an (n-1)ary tuple containing the rest of the tuple. If so then you could use partial function application and recursion to apply each argument one at a time. I guess the solution in the general case is to use a list of arguments instead of a tuple?

By on 11/18/2008 1:58 PM ()

Right, because you cannot generalize on the length of a tuple, statically you always know the length of the tuple, so an "arbitrary n-ary tuple" never exists. So, yes, what you are probably wanting is a list.

By on 11/18/2008 2:28 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper