Back to Questions
2.3k
views4
comments
Stringly Typed Heterogeneous Collections
f#collections

Hi! I am trying to build heterogeneous lists in F# with static duck typing, so far with disappointing results. The incriminated snippet is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

type Zero = Zero

type Succ{ ^a } = Succ of ^a

type HNil = HNil

type HCons{ 'hd,'tl } = HCons of ('hd * 'tl)

type HLookup{ ^hd, ^tl >() =

  static member inline lookup (HCons(hd,tl) : HCons{ ^hd,^tl >, z : Zero) = hd

type HLookup{ ^hd, ^tl, ^n, ^v, ^li when ^li : (static member lookup : (^tl * ^n) -} ^v)>() =

  static member inline lookup (HCons(hd,tl) : HCons{ ^hd,^tl >, Succ(n) : Succ{ ^n >) = 

    let tlxn = (tl,n)

    in (^li : (static member lookup : (^tl * ^n) -} ^v) tlxn)

type Person = HCons<string, HCons<string, HCons<int, HNil>>>

let (person:Person) = HCons("John", HCons("Doe", HCons(27, HNil)))

let first = HLookup<_,_>.lookup (person, Zero)

let last = HLookup<_,_,_,_,_>.lookup (person, Succ(Zero))

let age = HLookup<_,_,_,_,_>.lookup (person, Succ(Succ(Zero)))

in System.Console.WriteLine((first, last, age).ToString())

the library works (Zero, Succ, HNil, HCons and both HLookup). The lookup with last fails requesting more type annotations...

Sigh, with this F# would be on par with Haskell, or maybe even better given the hugely superior library support!

PS: I have replaced angle brackets with { and } since I cannot seem to obtain the rich editor for my posts :(

.

This works for me:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

type Zero = Zero 
type Succ< ^a > = Succ of ^a 
type HNil = HNil 
type HCons< 'hd,'tl > = HCons of ('hd * 'tl) 
type HLookup< ^hd, ^tl >() =
  static member inline lookup (HCons(hd,tl) : HCons< ^hd,^tl >, z : Zero) = hd 
type HLookup< ^hd, ^tl, ^n, ^v, ^li when ^li : (static member lookup : ^tl * ^n-> ^v)>() =
  static member inline lookup (HCons(hd,tl) : HCons< ^hd,^tl >, Succ(n) : Succ< ^n >) = 
    let tlxn = (tl,n) in (^li : (static member lookup : ^tl * ^n -> ^v) (tl, n))     
let person = 
  HCons("John", HCons("Doe", HCons(27, HNil))) 
let first = HLookup<_,_>.lookup (person, Zero)
let last = HLookup<_,_,_,_,HLookup<_,_>>.lookup(person, Succ(Zero))
let age = HLookup<_,_,_,_,HLookup<_,_,_,_,HLookup<_,_>>>.lookup (person, Succ(Succ(Zero)))

Note that I changed the constraint on ^li's lookup member from 

1

(^tl * ^n) -> ^v

<string, hcons=""><string, hcons=""><int, hnil=""></int,></string,></string,> to the seemingly identical 

1

^tl * ^n -> ^v

<string, hcons=""><string, hcons=""><int, hnil=""></int,></string,></string,>. However, for member constraints these types are very different - the first requires a single argument of a tuple type, while the second requires two distinct arguments. Alternatively, you could change the signature of HLookup<_,_>.lookup so that it takes a single tuple as its argument.

Having said all of that, I don't think that you'll be able to push this approach too far without running into more serious problems. F# was simply not designed for higher kinded programming in the same way that Haskell (or even Scala) is.

By on 7/28/2010 10:38 AM ()

Well, thanks! It is comforting to know that I had gotten so close :)

I believe that statically typed duck typing is far more powerful than we give it credit for. Should I complete my implementation of HLists (that is, removing all these annotations), I will move on to GADTs and type functions. If these can be encoded this way, then F# ha a type system that is on par with Haskell's...

By on 7/28/2010 12:27 PM ()

This is very interesting! Let us know how you go :-)

By on 7/29/2010 2:39 AM ()

This reminds me of similar solutions to the same problem that I've seen in strongly typed versions of Prolog, such as Borland's original Turbo Prolog*.

-Neil

*Now PDC Prolog, but I haven't used the newer versions so I don't know if my comment applies there.

By on 7/29/2010 7:33 AM ()

    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