[Haskell-cafe] Code Golf

[Jan Christiansen]

Hi,

On 15.04.2009, at 13:28, Sebastian Fischer wrote:

> Actually, there are a number of implementations that implement the  
> same behaviour as the original version, e.g.,
>
>  diag = concat . foldr diags []
>   where

>          diags []         ys       = ys
>          diags (x:xs)     ys       = [x] : merge xs ys
>
>          merge []         ys       = ys
>          merge xs@(_:_)   []       = map (:[]) xs
>          merge (x:xs)     (y:ys)   = (x:y) : merge xs ys


I think your first implementation is a slightly unreadable : )  
implementation of this version but uses functional lists instead of  
standard lists. If we replace some of the lists by functional lists we  
get the following

diag :: [[a]] -> [a]
diag = toList . concatFL . foldr diags2 []
  where
     diags [] ys = ys
     diags (x:xs) ys = (x:) : merge xs ys

     merge [] ys = ys
     merge xs@(_:_) [] = map (:) xs
     merge (x:xs) (y:ys) = ((x:) . y) : merge xs ys

with the following definitions

concatFL :: [[a] -> [a]] -> [a] -> [a]
concatFL = foldr (.) id

toList :: ([a] -> [a]) -> [a]
toList fl = fl []

Additionally we can move the 'map (:)' in merge to diags

diag :: [[a]] -> [a]
diag = toList . concatFL . foldr diags []
  where
     diags [] ys = ys
     diags (x:xs) ys = (x:) : merge (map (:) xs) ys

     merge [] ys = ys
     merge xs@(_:_) [] = xs
     merge (x:xs) (y:ys) = (x . y) : merge xs ys

If we now replace toList and concatFL by its definitions it looks very  
similar to the original implementation.

diag :: [[a]] -> [a]
diag = foldr (.) id (foldr diags []) []
  where
     diags [] ys = ys
     diags (x:xs) ys = (x:) : merge (map (:) xs) ys

     merge [] ys = ys
     merge xs@(_:_) [] = xs
     merge (x:xs) (y:ys) = (x . y) : merge xs ys

 > diag l = foldr (.) id ((sel l . flip sel) ((:[]).(:))) []
 >  where
 >   sel = foldr (\a b c -> id : mrg (a c) (b c)) (const []) . map  
(flip id)
 >
 >   mrg []     ys     = ys
 >   mrg xs     []     = xs
 >   mrg (x:xs) (y:ys) = (x.y) : mrg xs ys

I guess that we can inline diags and get the definition above but I am  
kind of stuck here.

Cheers, Jan