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

[Daniel Fischer]

On Friday 29 April 2011 16:07:00, philipp siegmantel wrote:
> Hi,
> 
> 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)

A different point of view:

given at least two lists, lists@(list1:more@(list2:_)), the longest common 
prefix of lists is the common prefix of list1 and the longest common prefix 
of more, so

longestCommonPrefix :: Eq a => [[a]] -> [a]
longestCommonPrefix [] = []  -- what else?
longestCommonPrefix lists = foldr1 commonPrefix lists

-- to get the common prefix of two lists, we use explicit recursion, I 
don't see an elegant way to avoid that.

commonPrefix :: Eq a => [a] -> [a] -> [a]
commonPrefix (x:xs) (y:ys)
    | x == y    = x : commonPrefix xs ys
commonPrefix _ _ = []

produces the result incrementally.