Jan Christiansen jac at informatik.uni-kiel.de
Wed Apr 15 08:12:35 EDT 2009

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

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