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 6 and 3 and type the answer here:
  • Post
  • 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))))))

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

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

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

       }

    }

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

  • i just wish someone had posted an Excel solution to this ;-)

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

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

  • 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

Page 3 of 3 (39 items) 123