Tight Code--A Puzzle in F#

Tight Code--A Puzzle in F#

  • Comments 39

Jomo Fisher--Luke Hoban wrote something in a blog entry that resonated with me:

One of the most striking features of F# code is that it is very terse - ideas can typically be expressed with a small amount of code. 

Don Syme once mentioned (I'm paraphrasing) that an aspirational goal for F# in the beginning was to make a compiler that could compile itself in less than 10,000 lines of code. Though that line count has since been passed I often get the sense that, with enough thought, I could boil whatever code I'm working on down to almost nothing.

Consider this coding problem (which I have since used as an interview question). Take a singly-linked-list of singly-linked-lists and pivot the inner values. For example say I have this list:

let have = [['a';'b';'1'];['c';'d';'2'];['e';'f';'3']]

Then the list I want is this:

let want = [['a';'c';'e'];['b';'d';'f'];['1';'2';'3']]

So the new list's first list has the first item from each of the original inner lists and so on. This problem actually came up in real-world piece of code I was working on. My first cut was procedural and about twenty lines of code. I don't have it here to show you, but after a few iterations and refactorings I got it down to a respectable nine lines:

let flatteninto source target =

    List.zip target source |> List.map(fun (head, tail)->head@[tail])

let pivot list =

    let rec work target = function

          head::tail-> work (flatteninto head target) tail

        | [] -> target

    let empties = list|>List.map(fun l->[])

    work empties list

At this point, I was stuck. It worked, but it seemed like there should be a better solution. In particular, the second to last line where I build up a list of empty lists didn't seem quite right. Being stuck, I asked my teammates whether there was a better solution out there. As it turns out, James Margetson had seen a beautiful four line solution to the problem.

I'll post the solution James showed me in a few days. In the meantime, I'd like to invite you to give the problem a try in the programming language of your choice. Can you cleanly beat my nine-line solution above? Can you get it down to four lines? I only ask that you don't change the input structure--singly-linked-list of singly-linked-list. Also, in my problem, the input was guaranteed to be well formed so I didn't need to check for jagged inner lists or other malformed inputs. Finally, notice that while I showed a 3x3 input in the example the dimensions don't have to be the same.

Update 11/20/2007 - Spoiler Alert!

As promised, here's the F# that James showed me

let rec transpose haves =

    match haves with

    | (_::_)::_ -> map hd haves :: transpose (map tl haves)

    | _         -> []

This is essentially the same as the Haskell algorithm that has been posted in the comments.

I want to thank the folks who posted solutions in various different languages--Scheme, Haskell, Ruby, C#, Python. Also, there was an OCaml solution which is indeed compatible with F#.

Several folks pointed out the analogy with matrix transpose. The code does get a lot easier when your input is an array of arrays, but you don't always get to pick your input representation.

One commenter opined that functional code may be easier to read than it is to write. This is true for me in one sense: there seems to always be a way to write the code a little better. Figuring out when I'm done is a challenge.

 

This posting is provided "AS IS" with no warranties, and confers no rights.

Leave a Comment
  • Please add 8 and 5 and type the answer here:
  • Post
  • >>> l = [['a','b','1'],['c','d','2'],['e','f','3']]

    >>> [list(i) for i in zip(*l)]

    [['a', 'c', 'e'], ['b', 'd', 'f'], ['1', '2', '3']]

    Is that what you're going for? 1 line of Python if it's not cheating to use zip.

  • let lolpivot (l : 'a list list) = [ for i in {0 .. (length (nth l 0))-1} -> [ for j in {0 .. (length l)-1} ->  nth (nth l j) i]];;

    It's not super pretty but it works

  • Matrix Transposition?  You could do it in (I think) 1 line of C#3, using indexing and List<T>'s ForEach method :)

    The immediate way I can see involves indexing operations, which can't be done directly in a singley-linked list, so my solution wouldn't be as efficient as James's, I suspect.

  • let rec pivot = function

    | [] -> []

    | [l] -> List.map (fun x -> [x]) l

    | l::ls -> List.map2 (fun x xs -> x::xs) l (pivot ls)

  • One line in S (to be more specific, the R implementation of the S language, www.r-project.org):

    # normally, you wouldn't use a nested list in S for this kind of data

    have <- list(list("a", "b", "1"), list("c", "d", "2"), list("e", "f", "3"))

    want <- do.call("mapply", args=c(list(FUN=c, SIMPLIFY=FALSE), have))

    This is similar to the Python example. Basically, I'm implementing the "zip" function on the fly. In contrast to "zip" in Python, the result isn't truncated to the length of the shortest entry if the entries of "have" aren't of the same length. Instead, shorter entries are "enlarged" by recycling their elements. If required, I'm sure one could change this to the Python behaviour in the very same line.

    Of course, if "have" is a matrix and you're after its transpose, you don't use a list in S:

    # turning "have" into a matrix (assuming each entry of "have" is a column

    have.matrix <- matrix(unlist(have), ncol=length(have))

    # its transpose

    t(have.matrix)

  • What you're looking for is the "zip" operator, it's a list transpose. (Isn't Zip in F#? It seems like you used it in your solution...)

    Zip is in python, like Jason Prado pointed out. There's a more succinct want to do the zip inverse, though - (this is python interactive output, the >>> means my input to the shell)

    >>> listOfLists = [['a','b','1'],['c','d','2'],['e','f','3'],['g', 'h', '4']]

    >>> zip(*listOfLists)

    [('a', 'c', 'e', 'g'), ('b', 'd', 'f', 'h'), ('1', '2', '3', '4')]

    The python * syntax unpacks a collection as the arguments to a function - func(*args) is shorthand for apply(func, args). Does F# have functional Apply?

    Here's an alternate implementation of inverse zip, using array indexing:

    >>> [[x[i] for x in listOfLists] for i in range(len(listOfLists[0]))]

    [['a', 'c', 'e', 'g'], ['b', 'd', 'f', 'h'], ['1', '2', '3', '4']]

  • Just for fun, here's how I'd do it procedurally in traditional C#:

    string[,] list = { { "a", "b", "1" }, { "c", "d", "2" }, { "e", "f", "3" } };

    for (int i = 0; i < list.GetLength(0); i++)

    {

       for (int j = 1 + i; j < list.GetLength(1); j++)

       {

           string tmp = list[i, j];

           list[i, j] = list[j, i];

           list[j, i] = tmp;

       }

    }

  • Sadly, this solution is five lines, but it'll do the trick:

    let rec pivot listOfLists =

     if List.hd listOfLists = [] then

       []

     else

       List.map (fun l -> List.hd l) listOfLists :: (pivot (List.map (fun l -> List.tl l) listOfLists))

  • let rec pivot listOfLists =

     if List.hd listOfLists = [] then

       []

     else

       List.map (fun l -> List.hd l) listOfLists :: (pivot (List.map (fun l -> List.tl l) listOfLists))

    Unfortunately, that's five lines. So close!

  • Got it to 4 lines:

    let rec pivot listOfLists =

     match listOfLists with

     | [] :: _ -> []

     | _ -> List.map (fun l -> List.hd l) listOfLists :: (pivot (List.map (fun l -> List.tl l) listOfLists))

  • I'm just beginning to learn OCaml / F#, so I'm sure this solution is ghastly to someone with better knowledge of the language. I'm looking forward to seeing the other solution.

    let rec combine a b = match a, b with

       | h1 :: t1, h2 :: t2 -> [ h1 :: h2 ] @ (combine t1 t2)

       | h :: t, [] -> [ [ h ] ] @ (combine t [])

       | _ -> [];;

    let rec pivot = function [] -> []

       | h :: t -> combine h (pivot t);;

  • Jason, why so verbose? It's a well-known python idiom:

    In [4]: zip(*x)

    Out[4]: [('a', 'c', 'e'), ('b', 'd', 'f'), ('1', '2', '3')]

    Do I get a job? :)

  • Oh, nevermind, he just changed the tuples to lists. Note to self: read before posting.

  • So, to make up for my failure to read Jason's comment, I asked myself how I would implement this without zip available. The obvious answer was to reimplement zip, and I did a rough approximation as a one-liner:

    def azip(*args):

       return [tuple([iter[x] for iter in args]) for x in xrange(len(args[0]))]

    In [40]: azip(*x)

    Out[40]: [('a', 'c', 'e'), ('b', 'd', 'f'), ('1', '2', '3')]

    Of course, you could change tuple() to list() to get Jason's version without the somewhat unsightly list comp.

  • Well this is my first F# program ever, and I'm no functional programmer, but here's what I have:

    let rec pivot(l: 'a list list) =

       match List.hd l with

           | head::tail -> [for sub in l -> List.hd sub]::pivot [for sub in l -> List.tl sub]

           | [] -> [];;

    It's four lines, unless you're shooting for 80 columns.  Kind of weird, but it works.

Page 1 of 3 (39 items) 123