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.