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