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