Tight Code–A Puzzle in F#


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 3×3 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.

Comments (39)

  1. Jason Prado says:

    >>> 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.

  2. pat marks says:

    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

  3. MSDNArchive says:

    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.

  4. Keith says:

    let rec pivot = function

    | [] -> []

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

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

  5. Torsten says:

    One line in S (to be more specific, the R implementation of the S language, http://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)

  6. Ian McMeans says:

    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’]]

  7. danieldsmith says:

    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;

       }

    }

  8. 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))

  9. 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!

  10. 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))

  11. Derek says:

    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);;

  12. Bill Mill says:

    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? 🙂

  13. Bill Mill says:

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

  14. Bill Mill says:

    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.

  15. Daniel Tang says:

    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.

  16. Bill Mill says:

    In haskell:

    Prelude> :m List

    Prelude List> transpose [[1,2,3],[3,4,5],[6,7,8]]

    [[1,3,6],[2,4,7],[3,5,8]]

    Where the definition of the transpose function is itself 4 lines long, and given in the List module: http://www.haskell.org/onlinelibrary/list.html . It’s quite a clever bit of code; while extremely simple, it would have taken me a lot of simplification to arrive at that result, if I ever did.

  17. Bill Mill says:

    And, finally, does the one-liner given here: http://caml.inria.fr/pub/ml-archives/caml-list/2007/03/9835735d060f8d8c7958467fa82914db.en.html in Ocaml work in F#? I find it really to be the least syntactically pleasing of the solutions, but that could be my unfamiliarity with OCaml talking.

  18. Steve Strong says:

    How about something like this in C# 3.0:

         static List<List<char>> Pivot(List<List<char>> have)

         {

            var x = new List<List<char>> { have.Select(l => l.First()).ToList() };

            return have.First().Count == 1 ?

                     x :

                     x.Union(Pivot(have.Select(l => l.GetRange(1, l.Count – 1)).ToList())).ToList();

         }

    How many lines of code depends on how you count it; I think I could argue 3 – one for the function declaration, one to assign x and one to return, however if you laid it out just using 3 lines in the text editor, it would be pretty unreadable 🙂  I’ll settle for 7.

  19. C# FP solution…

    without indexing…

    First() like car, Skip(1) like cdr

    static IEnumerable<IEnumerable<T>> Pivot<T>(IEnumerable<IEnumerable<T>> source)

    {

       if(!source.Any()) yield break;

       yield return source.Select(list => list.First());

    foreach(var value in Pivot(source.Select(list => list.Skip(1)).Where(list => list.Count() != 0)))

    yield return value;

    }

  20. Richard says:

    Mmmm…this is the best I could do in Java:

    static LinkedList<LinkedList> Pivot(LinkedList<LinkedList> list) {

    LinkedList<LinkedList> newList = new LinkedList<LinkedList>();

    //add new linkedlists

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

    newList.add(new LinkedList());

    //add the remaining objects to the linkedlists

    for (LinkedList ll : list) {

    Iterator<LinkedList> iter = newList.iterator();

    for (Object obj : ll) {

    iter.next().add(obj);

    }

    }

    return newList;

    }

  21. Scheme solution

    (define (pivot source)

     (if (null? source) ‘()

         (cons (map car source) (pivot (filter (lambda(x) (not (null? x))) (map cdr source))))))

  22. SteveStrong says:

    Completely forgot about using Skip(1), which cleans up my code a little:

    static IEnumerable<IEnumerable<char>> Pivot(IEnumerable<IEnumerable<char>> have)

    {

      var x = new List<IEnumerable<char>> { have.Select(l => l.First()) };

      return have.First().Count() == 1 ?

               x :

               x.Union(Pivot(have.Select(l => l.Skip(1))));

    }

    Gets rid of a load of those pesky ToList() calls that were making things look messy 🙂

  23. d2bg says:

    In F#:

    let pivot = function

    | [] -> []

    | h::_ as l -> List.fold_right (List.map2 (fun x y -> x::y)) l [for i in h -> []];;

  24. Jon Harrop says:

    (Math.Matrix.Generic.of_seq have).Transpose

  25. d2bg says:

    Another obscuer:

    let pivot =

     let rec aux c = function

       | [] | [[]] | []::[]::_  -> c ([],[])

       | []::l -> aux (fun (rh,rt) -> c([],rh::rt)) (l@[[]])

       | (h::t)::l -> aux (fun (rh,rt) -> c (h::rh, rt)) (l@[t]) in

     fun l -> aux snd ([]::l);;

  26. Matt Youell says:

    I took a crack at this in Erlang, something I’m just learning. Erlang actually has a function to zip 3 lists together but making it work with a list of lists as input was awkward and didn’t scale to lists > 3, etc. So I ended up with this:

    pivot([]) -> [];

    pivot(List) ->

    [ [Head || [Head | _] <- List] ] ++ pivot([Tail || [_ | Tail] <- List]).

    %% Then the calling code looks like:

    Want = pivot(Have).

  27. tomasp says:

    If you choose the right representaton than you can do it with one character in Matlab, just as a matrix transposition 🙂 – similarly to the F# solution posted by Jon Harrop that uses F# matrices.. in Matlab it would look like this:

    >> have = [‘a’ ‘b’ ‘1’; ‘c’ ‘d’ ‘2’; ‘e’ ‘f’ ‘3’];

    >> have’

    [‘a’ ‘c’ ‘e’; ‘b’ ‘d’ ‘f’; ‘1’ ‘2’ ‘3’];

    🙂 ..but I think that the important question is – how to implement this directly on functional (linked) list type and without using inefficient ‘nth’ function and any built-in matrix transpositions. That’s more tricky question :-). My F# solution looks like this:

    let rec transpose have =

     let (res, rem, cont) = List.fold_right (fun (h::t) (res,tmp,_) -> (h::res,t::tmp,t<>[])) have ([],[],true)

     res::(if cont then transpose rem else [])

    It’s doing fold_right for every returned row, which internally uses one List.rev, which is inefficient, but I think that it will have to be used in any solution… It also reports one compiler warning, but that’s fine, because the problematic case cannot occur for non-empty input.

  28. Christer says:

    I found the Haskell code and compared it with my Ruby version of transpose.

    (Array.transpose is built in, but I redefined it.)

    I think the Haskell code is better.

    # Haskell code:

    # transpose []             = []

    # transpose ([]     : xss) = transpose xss

    # transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) :

    #          transpose (xs : [t | (h:t) <- xss])

    class Array

     def transpose

       return [] if self == []

       head,*tail = self

       return tail.transpose if head==[]

       h,*t = head

       [[h] + tail.collect{|_| _[0]}] + ([t] + tail.collect{|_| _[1,size-1]}).transpose

     end

    end

    assert [[‘a’,’c’,’e’],[‘b’,’d’,’f’],[‘1′,’2′,’3’]], [[‘a’,’b’,’1′],[‘c’,’d’,’2′],[‘e’,’f’,’3′]].transpose

  29. Christer says:

    That F# 4-liner was amazing!

    Inspired me to improve my Ruby code.

    But your F# is much more elegant!

     def transpose

       return [] if self == []

       return tail.transpose if head==[]

       [map{|e| e.head}] + (map{|e| e.tail}).transpose

     end

  30. tomasp says:

    The Haskell solution is very elegant (and also more efficient than the code that I posted earlier). Using the F# syntax it looks like this:

    let rec transpose = function

     | [] -> []

     | []::xss -> transpose xss

     | (x::xs)::xss -> (x::[for h::t in xss -> h])::

                       (transpose(xs::[for h::t in xss -> t]))

  31. bhrgunatha says:

    The scheme solution seems the most elegant to me.

    My solution is identical except I chose to bail at the end of the shortest list.

    (define (flip xss)

     (cond ((not (null? (filter (lambda (l) (null? l)) xss))) ‘())

           (exsse (cons (map car xss)

                       (flip (map cdr xss))))))

  32. Raptor-75 says:

    Here’s my solution using C# 3.0 / LINQ:

    static IEnumerable<IEnumerable<T>> TransposeWithIndexGroupBy<T>(IEnumerable<IEnumerable<T>> source)

    {

       return source.SelectMany(list => (list.Select((value, index) => new { Value = value, Index = index })))

                    .GroupBy(tuple => tuple.Index, tuple => tuple.Value, (key, list) => list);

    }

    What it does is take each char and put it in an anonymous type together with its inner list index. It then flattens the whole thing to a single list (SelectMany) and finally groups by inner index. The last two paramaters to GroupBy gets rid of the anonymous type and the grouping key respectively. In reality though it’s probably not executed one step at a time like I described it.

    It’s actually at least 3 times faster than SteveStrong’s solution and at least 5 times faster than Nick Palladinos’ solution.

  33. SteveStrong says:

    Nice one, Raptor-75.  I think I still prefer mine for it’s readability, but there’s no doubt you win hands-down on line count & perf!

  34. (C#)

    I think when trying to find an elegant solution to a problem like this, it can be handy to derive the solution from first principles – in the case of list-y stuff, "how do I get the first result?" and "how do I recurse to get the rest?"  Here we have

    [[ab1][cd2][ef3][gh4]]

    and we want

    [[aceg][bdfh][1234]]

    So we first ask, how can we get the first element of "want"?  It is clear that this is

    have.Select(l => l.First())

    Having consumed those values, we now want to recurse with a have-like list that would yield the next wanted value, and we can see that we want to recurse with

    [[b1][d2][f3][h4]]

    in order for the same Select() call to produce the second element of want.  And we can see that

    [[b1][d2][f3][h4]]

    is just

    have.Select(l => l.Skip(1))

    At that point there’s enough insight to easily write the code.

    Anyway, that was my thought process, here’s a full C# program.

    using System;

    using System.Collections.Generic;

    using System.Linq;

    static class Program

    {

       public static IEnumerable<T> Cons<T>(T x, IEnumerable<T> rest)

       {

           yield return x;

           foreach (T t in rest)

               yield return t;

       }

       public static bool IsEmpty<T>(this IEnumerable<T> list)

       {

           return !list.GetEnumerator().MoveNext();

       }

       static IEnumerable<IEnumerable<T>> Transpose<T>(IEnumerable<IEnumerable<T>> lol)

       {

           return lol.IsEmpty() || lol.First().IsEmpty()

               ? Enumerable.Empty<IEnumerable<T>>()

               : Cons(lol.Select(l => l.First()),

                      Transpose(lol.Select(l => l.Skip(1))));

       }

       static void Display(IEnumerable<IEnumerable<char>> lol)

       {

           foreach (IEnumerable<char> l in lol)

           {

               foreach (char c in l)

               {

                   Console.Write(c);

               }

               Console.WriteLine();

           }

       }

       static void Main(string[] args)

       {

           IEnumerable<IEnumerable<char>> lol = new[]{

               new [] { ‘a’, ‘b’, ‘1’ }.AsEnumerable(),

               new [] { ‘c’, ‘d’, ‘2’ }.AsEnumerable(),

               new [] { ‘e’, ‘f’, ‘3’ }.AsEnumerable(),

               new [] { ‘g’, ‘h’, ‘4’ }.AsEnumerable()

           }.AsEnumerable();

           Display(lol);

           Display(Transpose(lol));

           // Here’s a mental picture of the process:

           // answer                                            remaining input

           //                                                   [[ab1][cd2][ef3][gh4]]

           // Cons([aceg], …                                  [ [b1] [d2] [f3] [h4]]

           // Cons([aceg], Cons([bdfh], …                     [  [1]  [2]  [3]  [4]]

           // Cons([aceg], Cons([bdfh], Cons([1234], …        [   []   []   []   []]

           Console.ReadKey();

       }

    }

  35. Tony Nassar says:

    I knew I’d seen this in a textbook, and I had. It’s probably in lots of textbooks, but I remembered it from William Clocksin’s <i><a href ="http://books.google.com/books?id=QwzQwVUzR2MC&pg=PA70&lpg=PA70&dq=prolog+clocksin+transpose&source=web&ots=nFIOlNQkz_&sig=H8ZG9Hj9gVUNX7EJp-sDst7wVK0#PPA70,M1">Clause and Effect: Prolog Programming</i>. Btw, I think that Raptor-75’s solution is the only one that’s "tail recursive." Am I correct?

  36. secretGeek says:

    i just wish someone had posted an Excel solution to this 😉

  37. Mr Wonderful says:

    If this is a language competition then Matlab clearly wins.  It takes less than a line.  Heck, it’s barely a character:

       want = have’

    Transpose is done with the apostrophe char (‘).

  38. Ben says:

    That’s a bit of a cheat, it’s five lines if you include the "open List", without which it don’t compile…

  39. bistok says:

    From the Expert F# book, make it tail recursive:

    open List

    let rec transpose (haves: ‘a List List) (acc : ‘a List List) =

       match haves with

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

       | _ ->rev acc