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 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.
Comments
Anonymous
November 17, 2007
The comment has been removedAnonymous
November 17, 2007
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 worksAnonymous
November 17, 2007
The comment has been removedAnonymous
November 17, 2007
let rec pivot = function | [] -> [] | [l] -> List.map (fun x -> [x]) l | l::ls -> List.map2 (fun x xs -> x::xs) l (pivot ls)Anonymous
November 17, 2007
The comment has been removedAnonymous
November 17, 2007
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']]Anonymous
November 17, 2007
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; } }Anonymous
November 17, 2007
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))Anonymous
November 17, 2007
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!Anonymous
November 17, 2007
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))Anonymous
November 17, 2007
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);;Anonymous
November 17, 2007
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? :)Anonymous
November 17, 2007
Oh, nevermind, he just changed the tuples to lists. Note to self: read before posting.Anonymous
November 17, 2007
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.Anonymous
November 17, 2007
The comment has been removedAnonymous
November 17, 2007
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.Anonymous
November 17, 2007
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.Anonymous
November 18, 2007
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.Anonymous
November 18, 2007
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; }Anonymous
November 18, 2007
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; }Anonymous
November 18, 2007
Scheme solution (define (pivot source) (if (null? source) '() (cons (map car source) (pivot (filter (lambda(x) (not (null? x))) (map cdr source))))))Anonymous
November 18, 2007
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 :)Anonymous
November 18, 2007
In F#: let pivot = function | [] -> [] | h::_ as l -> List.fold_right (List.map2 (fun x y -> x::y)) l [for i in h -> []];;Anonymous
November 19, 2007
(Math.Matrix.Generic.of_seq have).TransposeAnonymous
November 19, 2007
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);;Anonymous
November 19, 2007
The comment has been removedAnonymous
November 19, 2007
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.Anonymous
November 20, 2007
The comment has been removedAnonymous
November 20, 2007
The comment has been removedAnonymous
November 20, 2007
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]))Anonymous
November 22, 2007
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))))))Anonymous
November 24, 2007
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.Anonymous
November 29, 2007
The comment has been removedAnonymous
December 06, 2007
(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(); } }Anonymous
December 07, 2007
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?Anonymous
December 20, 2007
i just wish someone had posted an Excel solution to this ;-)Anonymous
August 01, 2008
The comment has been removedAnonymous
December 17, 2008
The comment has been removedAnonymous
April 05, 2009
The comment has been removed