Manacher Algorithm in Haskell

Question

Please review the manacher algorithm in haskell. Find the longest Palindrome in a String.

module Main where
import qualified Data.Vector as V
import Data.Maybe
import Data.Ord
-- manacher algorithm
-- $ ghci
-- $ :l manacher.hs
-- > manacher "aba"
manacher :: String -> String
manacher arg0 = filter (/= '|') . V.toList $ maximum' getList
 where
 getList :: [V.Vector Char]
 getList = foreveryvchars 1 $ format arg0
 
-- get the maximum length palindrome
maximum' :: [V.Vector Char] -> V.Vector Char
maximum' = foldr1 (\x y -> if V.length x > V.length y then x else y)
-- for every character try to match the left with right side
foreveryvchars :: Int -> V.Vector Char -> [V.Vector Char]
foreveryvchars center vchars =
 case vchars V.!? center of
 Nothing -> []
 _ -> let (k, v) = match center 1 vchars
 in v : foreveryvchars
 ((\x -> if x == 0 then center + 1 else center + x) k) vchars
-- Takes the center and expand till it matches
-- returns the length and the palindrome it found around the center
match::Int -> Int -> V.Vector Char -> (Int, V.Vector Char)
match center radius vchars = let left = getleft center radius vchars
 right = getright center radius vchars
 in
 case left /= Nothing && right /= Nothing && left == right of
 True -> match center (radius + 1) vchars
 _ -> (radius - 1, V.slice (center - (radius - 1) ) (1 + ((radius -1 ) * 2)) vchars)
 
getleft center radius vchars = vchars V.!? (center - radius)
getright center radius vchars = vchars V.!? (center + radius)
-- 
format :: String -> V.Vector Char
format = stov . convert
-- Insert pipe after each character
convert::String -> String
convert [] = '|':[]
convert (x:xs) = '|':x:convert xs
-- Convert String to Data.Vector
stov::String -> V.Vector Char
stov = V.fromList
main::IO()
main = print "hello world"

Answer 1

Write clearly.

Adding comments to your functions is good, but your first choice should be for the functions (and their arguments) to have self-explainatory names. Second, one hopes that the type signature will explain what the function does (sometimes adding type aliases can help with this). Only then, if there's still details that need explanation, write the comments in clear, complete sentences. Alternately, I think it's fine to just give a URL to a canonical source for the function.

Additionally, any time there's a part of the code you struggled with or had to scrap an attempt at, try to leave a comment explaining why you ended up with the solution you did.

match says it returns the "length", but the thing it actually returns is more like the "radius".

Also, be a little more careful with your whitespace. Also camel-case and pascal-case are conventional in Haskell, e.g. sToV.

Use -Wall.

It stands for "warnings: all". Use it to find places where GHC already knows you can improve your code. Unfortunately, it doesn't actually mean "all", there are other flags you can set to make GHC even pickier.

Sometimes less is more. Sometimes more is more.

If there's a particular parametric type you use a lot, give it an alias (or a newtype, depending on the situation) like type PaddedVec = V.Vector (Maybe Char).
On the other hand, if you have an alias (like stov) that you only use once, probably just inline it. If you want to be named, you can group it with its usage with a where clause.

Be sure you're using built-in functionality as well as you can.

• maximum' is "just" maximumBy (compare `on` V.length).
• You can use where together with guards to simplify the function you were calling match.
• Ironically, in Haskell you rarely actually need to use a lambda.

Adding a bunch of '|' chars isn't great.

It's not clear that there's a better solution that doesn't involve any padding at all (I tried and failed), but choosing an arbitrary "dummy" character could fail (if the source text contains that character), and it locks your implementation to the one data-type (Char). Consider for example how you would adapt this algorithm to work on lists of integers? I would suggest instead mapping all the values to Justs, and padding with Nothing.

here's my version:

module Main where
import Data.Foldable (maximumBy)
import Data.Function (on)
import Data.Maybe (catMaybes)
import qualified Data.Vector as V
type PaddedVec a = V.Vector (Maybe a)
-- https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher.27s_algorithm
manacher :: (Eq a) => [a] -> [a]
manacher = catMaybes . V.toList . grabLongest . scan . V.fromList . padded
 where grabLongest = maximumBy (compare `on` V.length)
 padded [] = Nothing : [] -- Can't just use Data.List.intersperse; we need them wrapping outside too.
 padded (x : xs) = Nothing : Just x : padded xs
 scan = forEveryIndex 0 -- Starting at 1 could cause a fold1-exception if the input is empty
-- For every index, find the largest palindrome centered there, skipping some per Manacher's algorithm.
forEveryIndex :: (Eq a) => Int -> PaddedVec a -> [PaddedVec a]
forEveryIndex center vec = if center < (V.length vec)
 then pal : forEveryIndex (center + (max 1 radius)) vec
 else []
 where (pal, radius) = findAround center 1 vec
-- Find the longest palindorme centered at an index (and its "radius").
findAround :: (Eq a) => Int -> Int -> PaddedVec a -> (PaddedVec a, Int)
findAround center radius vec
 | Nothing <- left = (priorSlice, priorRadius) -- This is an "outer" Nothing. 
 | Nothing <- right = (priorSlice, priorRadius)
 | left /= right = (priorSlice, priorRadius)
 | otherwise = findAround center (radius + 1) vec
 where left = vec V.!? (center - radius) -- left :: Maybe (Maybe a)
 right = vec V.!? (center + radius) -- use `forall a.` above to make these explicit.
 priorRadius = radius - 1
 priorSlice = V.slice (center - priorRadius) (1 + (priorRadius * 2)) vec
main :: IO()
main = do print $ manacher "hello world"
 print $ manacher "abacaba"
 print $ manacher "helloll world"
 print $ manacher "helloll wowrld"
 print $ manacher ""
 print $ manacher "x"