Nov 072011
 

Although F# seems to have no tuple size limit there’s no primitive functions to “expand” a tuple.
Tuples are intended to be composed and decomposed as Algebraic Data Types, there are only 2 functions provided: fst and snd, and they work only with a 2-uple.
We can build functions with overloads for each arity, up to a reasonable size, the problem with this approach is that we will have a lot of repetitive code for each function.
To avoid the repetitive code, one approach is to use a code generator.
Another approach is to define the primitives functions repeating code and using inline for the rest of the functions.
We can think of a tuple as a list, so the primitives are cons and split in head-tail.
We’ll need a way to represent the 0-uple and a single element 1-uple. For the 1-uple we will a type called Singleton and for the empty tuple we will use the unit value ().

type Singleton<'a>   = Singleton of 'a

type Split = Split with
    static member ($) (Split, Singleton x1    ) = (x1, ())
    static member ($) (Split, (x1,x2)         ) = (x1, Singleton x2)
    static member ($) (Split, (x1,x2,x3)      ) = (x1, (x2,x3))
    static member ($) (Split, (x1,x2,x3,x4)   ) = (x1, (x2,x3,x4))
    static member ($) (Split, (x1,x2,x3,x4,x5)) = (x1, (x2,x3,x4,x5))
 
type Join = Join with
    static member ($) (Join, ()           ) = fun x -> Singleton x
    static member ($) (Join, Singleton x1 ) = fun x -> (x,x1)
    static member ($) (Join, (x1,x2)      ) = fun x -> (x,x1,x2)
    static member ($) (Join, (x1,x2,x3)   ) = fun x -> (x,x1,x2,x3)
    static member ($) (Join, (x1,x2,x3,x4)) = fun x -> (x,x1,x2,x3,x4)

let inline (|Cons|) tuple   = Split $ tuple
let inline Cons (head,tail) = Join $ tail <| head

Functions to be implemented:
Cons – Will be implemented also as an active pattern so we can go both ways.
Rev – Reverse the elements of the tuple.
Map – Map a function into a tuple with elements of the same type.
Fold – Will work also with tuples with elements of the same type.
<*> – Apply each function of the first tuple to the corresponding element of the second tuple. For Haskellers this will be like the <*> operator for the ZipList applicative functor.

We’ll need to define a binary operator, but the first parameter will be the type that represent the function.
As operator we’ll use ($), the Haskell equivalent of (<|) which should be read as 'apply'. Some functions take 2 parameters, so for the second parameter we may need to use parenthesis, because the binary operator has precedence over the apply: f a1 a2 = (f $ a1) a2 But we will use the idiomatic F# 'apply' (<|) f $ a1 <| a2 In some cases we will swap the order of the parameters, because we need the tuple to participate in the ($) operator resolution to select the right overload. Having implemented the primitives, before doing the rest of the functions, let's think how would they look for lists.

let rec Rev list ac = match list with
                      | x::xs -> Rev xs (x::ac) 
                      | []    -> ac
let rev list = Rev list [] 

let rec Map list f = match list with
                     | x::xs -> f x :: Map xs f
                     | []    -> []
let map f list = Map list f

let rec Fold list f z = match list with
                        | x::xs -> Fold xs f (f z x)
                        | []    -> z
let fold f z list = Fold list f z

let rec Ap fnList list = match fnList with
                         | f::fs -> let (x::xs) = list in (f x :: Ap fs xs)
                         | []    -> []
let (<*>) fnList list = Ap fnList list

Let’s do it point-free.

let rec Rev = function
    | x::xs -> fun ac -> Rev xs (x::ac) 
    | []    -> id
let rev list = Rev list []

let rec Map = function
    | x::xs -> fun f -> f x :: Map xs f
    | []    -> fun _ -> []
let map f list = Map list f

let rec Fold = function
    | x::xs -> fun f z -> Fold xs f (f z x)
    | []    -> fun _ x -> x
let fold f z list = Fold list f z

let rec Ap = function
    | f::fs -> fun (x::xs) -> (f x :: Ap fs xs)
    | []    -> fun _       -> []
let (<*>) fnList list = Ap fnList list

List with different number of elements may share the same type, this is not true with tuples.
For tuples we will go from one type to another all the time.
Remember in previous post the rules to translate a value-level to a type-level implementation?

“for each case in the discriminated union create a separate type, for each case in the match create different overloads of the same method”

We already have different types: () , Singleton, (,) , (,,) , (,,,) and so on. The difference is now we’re using existing types, except for Singleton.
But then in the first post of these series we faced that problem, the solution when we don’t have access to the source code of the type was

“use a DU as intermediate type, implement an operator as static member, accepting an unused parameter which is a value of the DU and the other parameter is overloaded”

So, the same functions for tuples could be written this way:

type Rev = Rev with
    static member inline ($) (Rev, Cons(x,xs)) = fun ac -> Rev $ xs <| Cons(x,ac)
    static member        ($) (Rev, ()        ) = id
let inline rev tuple = Rev $ tuple <| ()

type Map = Map with
    static member inline ($) (Map, Cons(x,xs)) = fun f -> Cons(f x, Map $ xs <| f)
    static member        ($) (Map, ()        ) = fun _ -> ()
let inline map f tuple = Map $ tuple <| f

type Fold = Fold with
    static member inline ($) (Fold, Cons(x,xs)) = fun f z -> Fold $ xs <| f <| f z x
    static member        ($) (Fold, ()        ) = fun _ x -> x
let inline fold f z tuple = Fold $ tuple <| f <| z

type Ap = Ap with
    static member inline ($) (Ap, Cons(f,fs)) = fun (Cons(x,xs)) -> Cons(f x, Ap $ fs <| xs)
    static member        ($) (Ap, ()        ) = fun _            -> ()
let inline (<*>) fnTuple tuple = Ap $ fnTuple <| tuple

A quick test

> rev (1, "second", [3], 4.0) ;;
val it : float * int list * string * int = (4.0, [3], "second", 1)

> map ((+) 10) (5, 15, 25) ;;
val it : int * int * int = (15, 25, 35)

> map string (5, 15, 25) ;;
val it : string * string * string = ("5", "15", "25")

> fold (+) 0 (5, 15, 25) ;;
val it : int = 45

> ((+), (*)) <*> (2, 5.5) <*> (3, 2.0) ;;
val it : int * float = (5, 11.0)

Some functions make more sense with lists, otherwise we are restricted to a tuple of elements of the same type, but in the case of the operator <*> it’s the opposite, it will be more interesting with tuples than with lists because it will be able to operate with different types.

Another interesting function could be nth, but we can’t use integers, because we can’t select a type based on a value.
What we can do is select type based on another type.
Remember Peano numbers?

type Zero     = Zero with
    static member inline (|!|) (Cons(x,_),Zero) = x
 
type Succ<'a> = Succ of 'a with
    static member inline (|!|) (Cons(_,xs),Succ p) = xs |!| p

let inline nth tuple  n = tuple |!| n

Now we can access any element without losing type information.


> let I = Succ Zero ;;
val I : Succ<Zero> = Succ Zero

> let II = Succ I ;;
val II : Succ<Succ<Zero>> = Succ (Succ Zero)

> nth (50, 'b', "F# is fun") Zero ;;
val it : int = 50

> nth (50, 'b', "F# is fun") I ;;
val it : char = 'b'

> nth (50, 'b', "F# is fun") II ;;
val it : string = "F# is fun"

Conclusion

In this post we used and abused of recursive inline functions at the point we’re killing the compiler.
We integrated two different techniques we saw individually in previous posts.
In the next post we will concentrate and refine more this technique.

  One Response to “Inline Fun Part III – Functions for Tuples”

  1. Multiplying 3 by 4 makes the compiler run forever. But now I learned that F# type inference can be exponential time.
    C# compiler hangs:
    http://codegolf.stackexchange.com/questions/24401/so-obviously-p-np
    http://stackoverflow.com/questions/1162362/nested-linq-min-crashes-visual-studio

 Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>