[Haskell-beginners] Longest common prefix of a list of lists

philipp siegmantel philipp.siegmantel at googlemail.com
Fri Apr 29 16:07:00 CEST 2011


For one of my toy project I had to find the longest common prefix of a list
of strings.
I figured, that this function should only work on list-structure, meaning it
should have type

> longestCommonPrefix :: [[a]] -> [a]

Sadly the best I could come up with was using explicit recursion. It works
as far as I tested it, but I have the feeling that there's a better way to
do it.
Here is the code:

> longestCommonPrefix :: Eq a => [[a]] -> [a]
> longestCommonPrefix []   = []
> longestCommonPrefix xss | any null xss = []
>                                        | otherwise    = loop xss []
>  where loop ::Eq b => [[b]] -> [b] -> [b]
>            loop xss acc =
>              let xs = concatMap (take 1) xss
>              in if any (\x -> x /= head xs) (tail xs)
>                  then reverse acc
>                  else loop (map tail xss) (head xs : acc)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20110429/28412382/attachment.htm>

More information about the Beginners mailing list