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

aditya siram aditya.siram at gmail.com
Sat Apr 30 01:10:33 CEST 2011

-- 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)) .

 Trial runs:
   > commonPrefix [a,b] => "abab"
   > commonPrefix [a,b,c] => "ab"
   > commonPrefix [a,b,c,d] => ""

 '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]] =>
      maybeTranspose [[1,2][][4,5]] =>
                     [[Just 1,Nothing,Just 4],
                      [Just 2,Nothing,Just 5],

 '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

  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.

More information about the Beginners mailing list