Pointfree diagonalization in Haskell

[kpreid]

James@Waterpoint (Xplat on Freenode) mentioned an interesting problem: write an elegant point-free expression to compute the diagonal of a list of lists (that is, from [[00, 01, 02, ...], [10, 11, 12, ...], ...] obtain [00, 11, ...]).

His version:

diag = (map head) . (foldr (flip ((flip (:)) . (map tail))) [])

My version, which needs a non-pointfree helper function (but one which others have invented before, and perhaps ought to be in the standard libraries), but has fewer flips:

import Control.Arrow ((***))
import Data.List (unfoldr)

uncons xs = case xs of (x:xs') -> Just (x,xs'); [] -> Nothing
diag = unfoldr (fmap (head *** (map tail)) . uncons)

uncons is sort of the opposite of unfoldr, in that unfoldr uncons = id.

Update: darius's version, from the comments:

diag = flip (zipWith (!!)) [0..]

Comments

[darius.livejournal.com]

How about

diag = flip (zipWith (!!)) [0..]

?

[kpreid.livejournal.com]

You win.

[asviraspossible.livejournal.com]

ROFL

[(Anonymous)]

Any list code using !! is broken. :)

Fun!

[(Anonymous)]

I ended up with zipWith ($) (iterate (. tail) head) Is there some nicer way to express 'zipWith ($)'? It seems like there should be.

Re: Fun!

[(Anonymous)]

There are even two ways to do this. You could use (<*>) which uses the Applicative instance for lists as well as ap which uses the Monad instance for lists.

Re: Fun!

[(Anonymous)]

Just after pressing the "post comment" button I realize that I have written nonsense. The instances for the list type use the non-determinism view of lists. You have to use the ZipList newtype wrapper (http://www.haskell.org/hoogle/?hoogle=ZipList) to achieve the desired behaviour.