[Haskell-beginners] Longest common prefix of a list of lists
daniel.is.fischer at googlemail.com
Fri Apr 29 16:32:39 CEST 2011
On Friday 29 April 2011 16:07:00, philipp siegmantel wrote:
> 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.
More information about the Beginners