Log in

Kevin Reid's blog

Pointfree diagonalization in Haskell


Kevin Reid
My Website

Pointfree diagonalization in Haskell

Previous Entry Share Next Entry

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..]
Powered by LiveJournal.com