Berlekamp–Massey Algorithm in Haskell I was recently tasked to write an implementation of the Berlekamp–Massey algorithm (for GF2) from a given inductional proof and decided to fresh up on my Haskell, since converting a proof by induction into a recursive algorithm should be quite straight-forward.

The variable names have been taken from the given proof (and thus can't be changed, although they differ from other notations or are rather short); here's a map:


ks: the input bit stream
len: the length of ks
n: degree of the current annihilating polynomial
phi: said polynomial, where a "bit" set at position \$i\$ indicates that the the \$i\$-th power is "part" of the polynomial, ie.:
$$
      \varphi(X) = \sum_{i=0}^n \text{phi}[i] \cdot X^i
  $$
s, psi: analogously the degree and the polynomial itself of the last iteration that had different values
r: the maximum length of the prefix of ks that psi annihilates successfully
dl: the discrepancy between the annihilation by phi and the \$l\$-prefix of ks
eta: The new polynomial, calculated as:
$$
      \eta(X) = \varphi(X) + X^{l-r} \cdot \psi(X)
  $$


data State = State { n :: Int
                   , phi :: [Int]
                   , s :: Int
                   , psi :: [Int]
                   , r :: Int
                   }
    deriving Show

discr :: Int -&gt; [Int] -&gt; Int -&gt; [Int] -&gt; Int
discr l ks n phi = foldr (\ a k -&gt; (a+k) `mod` 2) 0
    (zipWith (*) (take (n+1) phi) (reverse $ take (n+1) $ drop (l-n) ks))

buildEta :: [Int] -&gt; [Int] -&gt; Int -&gt; Int -&gt; Int -&gt; [Int]
buildEta phi psi l r s
    = (take (l-r) phi) ++
      (zipWith (\ c b -&gt; (c+b) `mod` 2) (take (s+1) $ drop (l-r) phi) (take (s+1) psi)) ++
      (drop (l-r+s+1) phi)

bk' :: Int -&gt; [Int] -&gt; State
bk' (-1) ks = State 0 (1:lenzeroes) 0 (1:lenzeroes) (-1)
    where lenzeroes = replicate (length ks) 0
bk' l ks
    | dl == 0   = State n phi s psi r
    | n*2 &lt;= l  = State (l+1-n) eta n phi l
    | otherwise = State n eta s psi r
    where State n phi s psi r = bk' (l-1) (ks)
          dl = discr l ks n phi
          eta = buildEta phi psi l r s

bk :: [Int] -&gt; (Int,[Int])
bk ks = (n,phi)
    where State n phi _ _ _ = bk' (length ks) ks


I'm not quite happy with the result though, especially the buildEta function and the use of length.  I think the latter could be improved by reversing ks and then giving only the tail to the recursive call, but somehow I still need to build the phi and psi lists correctly, which I fail to do "nicely".

Style aside, the code works (as far as I know), eg.:

*Main&gt; bk [1, 0, 1, 0, 0, 1, 1, 0, 1]
(5,[1,0,1,0,1,1,0,0,0])


Which means that the degree of the polynomial is \$n\$ and it has the following form:
$$
\varphi = X^0 + X^2 + X^4 + X^5
$$
Or, as an LSFR, A=[1,1,0,1,0] which indeed generates ks with [1, 0, 1, 0, 0] as initialization sequence.



Edit: Had someone review my code offline and did some minor style fixes already:


some point-free style where appropriate
replacing some lambda with just (*)
replacing sum ()mod2 with foldr and lambda
found a way to rewrite the if-then-else into nice guards
replaced the list-comprehension for zeroes with replicate
line breaks :-)
A central question I ask myself on these is whether the explicit recursion follows an abstractable pattern. In this case, only bk' has explicit recursion, and its pattern is simple - the call tree is always linear and brings l incrementally down to -1.

buildEta applies a transformation to a particular slice of phi.

Why are you working with Ints? These are Bools.

bk :: [Bool] -&gt; (Int,[Bool])
bk ks = (n,phi) where
  State n phi _ _ _ = foldr (bk' ks) (State 0 lenzeroes 0 lenzeroes (-1)) [l,l-1..0]
  lenzeroes = True : replicate l False
  l = length ks

bk' :: [Bool] -&gt; Int -&gt; State -&gt; State
bk' ks l (State n phi s psi r)
  | not dl    = State n phi s psi r
  | n*2 &lt;= l  = State (l+1-n) eta n phi l
  | otherwise = State n eta s psi r
  where dl = discr l ks n phi
        eta = overSlice (l-r) (s+1) (zipWith xor psi) phi

discr :: Int -&gt; [Bool] -&gt; Int -&gt; [Bool] -&gt; Bool
discr l ks n = foldr xor False . zipWith (&amp;&amp;) (reverse $ take (n+1) $ drop (l-n) ks)

overSlice :: Int -&gt; Int -&gt; ([a] -&gt; [a]) -&gt; ([a] -&gt; [a])
overSlice from size f a = b ++ f d ++ e where
  (b, c) = splitAt from a
  (d, e) = splitAt size c