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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
