Berlekamp–Massey Algorithm in Haskell
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