Tight Code--A Puzzle in F#

re: Tight Code--A Puzzle in F#

Jason Prado — Sat, 17 Nov 2007 23:43:35 GMT

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

re: Tight Code--A Puzzle in F#

pat marks — Sun, 18 Nov 2007 00:01:13 GMT

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

re: Tight Code--A Puzzle in F#

kfarmer@microsoft.com — Sun, 18 Nov 2007 00:04:28 GMT

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.

re: Tight Code--A Puzzle in F#

Keith — Sun, 18 Nov 2007 00:56:56 GMT

let rec pivot = function

| [] -> []

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

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

re: Tight Code--A Puzzle in F#

Torsten — Sun, 18 Nov 2007 01:53:57 GMT

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)

re: Tight Code--A Puzzle in F#

Ian McMeans — Sun, 18 Nov 2007 02:39:10 GMT

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

re: Tight Code--A Puzzle in F#

danieldsmith — Sun, 18 Nov 2007 03:28:08 GMT

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;

}

re: Tight Code--A Puzzle in F#

Dustin Campbell — Sun, 18 Nov 2007 05:10:16 GMT

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

re: Tight Code--A Puzzle in F#

Dustin Campbell — Sun, 18 Nov 2007 05:17:04 GMT

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!

re: Tight Code--A Puzzle in F#

Dustin Campbell — Sun, 18 Nov 2007 05:20:17 GMT

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

re: Tight Code--A Puzzle in F#

Derek — Sun, 18 Nov 2007 06:10:06 GMT

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

re: Tight Code--A Puzzle in F#

Bill Mill — Sun, 18 Nov 2007 06:54:38 GMT

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

re: Tight Code--A Puzzle in F#

Bill Mill — Sun, 18 Nov 2007 06:55:27 GMT

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

re: Tight Code--A Puzzle in F#

Bill Mill — Sun, 18 Nov 2007 07:26:49 GMT

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.

re: Tight Code--A Puzzle in F#

Daniel Tang — Sun, 18 Nov 2007 08:27:42 GMT

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.

re: Tight Code--A Puzzle in F#

Bill Mill — Sun, 18 Nov 2007 08:40:19 GMT

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.

re: Tight Code--A Puzzle in F#

Bill Mill — Sun, 18 Nov 2007 08:50:00 GMT

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.

re: Tight Code--A Puzzle in F#

Steve Strong — Sun, 18 Nov 2007 16:31:13 GMT

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.

re: Tight Code--A Puzzle in F#

Palladinos Nick — Sun, 18 Nov 2007 20:27:31 GMT

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;

}

re: Tight Code--A Puzzle in F#

Richard — Sun, 18 Nov 2007 22:36:37 GMT

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;

}

re: Tight Code--A Puzzle in F#

Palladinos Nick — Mon, 19 Nov 2007 01:23:38 GMT

Scheme solution

(define (pivot source)

(if (null? source) '()

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

re: Tight Code--A Puzzle in F#

SteveStrong — Mon, 19 Nov 2007 12:24:22 GMT

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

re: Tight Code--A Puzzle in F#

d2bg — Mon, 19 Nov 2007 13:08:18 GMT

In F#:

let pivot = function

| [] -> []

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

re: Tight Code--A Puzzle in F#

Jon Harrop — Mon, 19 Nov 2007 17:31:38 GMT

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

re: Tight Code--A Puzzle in F#

d2bg — Mon, 19 Nov 2007 18:45:29 GMT

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

re: Tight Code--A Puzzle in F#

Matt Youell — Tue, 20 Nov 2007 00:51:10 GMT

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

re: Tight Code--A Puzzle in F#

tomasp — Tue, 20 Nov 2007 01:44:43 GMT

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.

re: Tight Code--A Puzzle in F#

Christer — Tue, 20 Nov 2007 18:46:43 GMT

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

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

re: Tight Code--A Puzzle in F#

Christer — Tue, 20 Nov 2007 22:40:27 GMT

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

re: Tight Code--A Puzzle in F#

tomasp — Wed, 21 Nov 2007 01:07:24 GMT

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

re: Tight Code--A Puzzle in F#

bhrgunatha — Fri, 23 Nov 2007 09:38:09 GMT

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

re: Tight Code--A Puzzle in F#

Raptor-75 — Sat, 24 Nov 2007 19:37:34 GMT

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.

re: Tight Code--A Puzzle in F#

SteveStrong — Fri, 30 Nov 2007 11:59:21 GMT

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!

re: Tight Code--A Puzzle in F#

Brian McNamara — Fri, 07 Dec 2007 15:20:55 GMT

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

}

re: Tight Code--A Puzzle in F#

Tony Nassar — Fri, 07 Dec 2007 17:56:39 GMT

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?

re: Tight Code--A Puzzle in F#

secretGeek — Thu, 20 Dec 2007 16:09:45 GMT

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

re: Tight Code--A Puzzle in F#

Mr Wonderful — Fri, 01 Aug 2008 22:46:44 GMT

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

re: Tight Code--A Puzzle in F#

Ben — Thu, 18 Dec 2008 10:38:51 GMT

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

re: Tight Code--A Puzzle in F#

bistok — Mon, 06 Apr 2009 07:50:30 GMT

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