-- Below is a solution that doesn't use length. -- Documentation for each function and trial runs -- are shown in a comment block at the end. import Data.List.Ordered(isSortedBy) import Safe(headMay) import Maybe(fromJust) a = "ababaaaa" b = "ababcccc" c = "ab" d = "" safeTail :: [a] -> [a] safeTail [] = [] safeTail xs = tail xs maybeTranspose :: [[a]] -> [[Maybe a]] maybeTranspose [] = [] maybeTranspose xs | all null xs = [] | otherwise = map headMay xs : maybeTranspose (map safeTail xs) commonPrefix :: Eq a => [[a]] -> [a] commonPrefix = map fromJust . fmap (head . snd) . takeWhile fst . fmap (\a -> ((isSortedBy (==) a), a)) . maybeTranspose {- Trial runs:
commonPrefix [a,b] => "abab" commonPrefix [a,b,c] => "ab" commonPrefix [a,b,c,d] => ""
Functions: 'safeTail' only returns the tail of the list of a non-empty list or an empty list 'maybeTranspose' is just like List.transpose except it returns the biggest matrix, not the smallest eg. transpose [[1,2],[],[4,5]] => [[1,4],[2,5]] maybeTranspose [[1,2][][4,5]] => [[Just 1,Nothing,Just 4], [Just 2,Nothing,Just 5], [Nothing,Nothing,Nothing]] 'commonPrefix' transposes the input lists , extracts the first n lists in the transposition where all the elements are equal, extracts the element from each and returns a concatenation of them. eg. Given input ["ab", "abab", "aba"] 1. Transpose [[Just 'a',Just 'a',Just 'a'], [Just 'b',Just 'b',Just 'b'], [Nothing,Just 'a',Just 'a'], [Nothing,Just 'b',Nothing]] 2. Tag lists with equal elements [(True,[Just 'a',Just 'a',Just 'a']), (True,[Just 'b',Just 'b',Just 'b']), (False,[Nothing,Just 'a',Just 'a']), (False,[Nothing,Just 'b',Nothing])] 3. Take the first n lists with equal elements [(True,[Just 'a',Just 'a',Just 'a']), (True,[Just 'b',Just 'b',Just 'b'])] 4. Grab the equal element from each [Just 'a',Just 'b'] 5. Concatenate "ab" I didn't like using 'fromJust' but I don't see how it can throw an exception in this case. Working with the (Bool, [Maybe a]) tuples directly could probably have been avoided by using Arrows, but it wasn't obvious to me. -}