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 5 and 4 and type the answer here:
  • Post
  • 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.

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

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

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

    }

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

    }

  • Scheme solution

    (define (pivot source)

     (if (null? source) '()

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

  • 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 :)

  • In F#:

    let pivot = function

    | [] -> []

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

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

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

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

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

  • 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

  • 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

  • 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]))

Page 2 of 3 (39 items) 123