Explains the process of polynomial long division

1Main.hs

import Poly (Field, inverse, Poly, x, polyDivModW)
import Control.Monad.Trans.Writer (execWriter)

newtype F2 = F2 Int
    deriving (Eq)

instance Show F2 where
    show (F2 x) = show x

instance Num F2 where
    (F2 a) + (F2 b) = fromIntegral $ a + b

    (F2 a) * (F2 b) = fromIntegral $ a * b

    (F2 a) - (F2 b) = fromIntegral $ a - b

    negate = id
    abs = id
    signum = id

    fromInteger = F2 . fromInteger . (`mod` 2)

instance Field F2 where
    inverse (F2 0) = undefined
    inverse (F2 1) = F2 1

main :: IO ()
main = mapM_ putStrLn $ execWriter $ polyDivModW
    (x^5 + x + 1 :: Poly F2)
    (x^2 + x + 1 :: Poly F2)

Poly.hs

module Poly
    (Field, inverse, (//), Poly(C), x, degree, leading, polyDivMod, polyDivModW)
    where

import Control.Monad.Trans.Writer (Writer, tell, censor)

-- Typeclass for Algebraic Fields
class Num a => Field a where
    (//) :: a -> a -> a
    a // b = a * inverse b
    inverse :: a -> a
    inverse a = 1 // a

-- Polynomial over any type
data Poly a
    = C a -- Constant Term
    | L a (Poly a) -- Constant Term plus x times a non-zero polynomial
        deriving (Eq)

-- Variable in polynomials
x :: Num a => Poly a
x = L 0 (C 1)

-- Returns the degree of non-zero polynomials
degree :: (Num a, Eq a) => Poly a -> Maybe Integer
degree (C 0) = Nothing
degree (C _) = Just 0
degree (L _ a) = succ <$> degree a

instance (Num a, Eq a) => Num (Poly a) where
    (C n) + (C m) = C (n+m)
    (C n) + (L m b) = L (n+m) b
    (L n a) + (C m) = L (n+m) a
    (L n a) + (L m b) = case a+b of
        C 0 -> C (n+m)
        c -> L (n+m) c
    (C 0) * _ = C 0
    _ * (C 0) = C 0
    (C n) * (C m) = C (n*m)
    (C n) * (L m b) = L (n*m) (C n * b)
    (L n a) * m = C n * m + L 0 (a*m)
    negate (C n) = C (negate n)
    negate (L n a) = L (negate n) (negate a)
    signum (C n) = C (signum n)
    signum (L _ a) = signum a
    abs a = a * signum a
    fromInteger = C . fromInteger

-- Helper for show that uses the current power of x
show' :: (Num a, Eq a, Show a) => Integer -> Poly a -> String
show' 0 (C n) = show n
show' 1 (C 1) = "x"
show' 1 (C n) = show n ++ "*x"
show' k (C 1) = "x^" ++ show k
show' k (C n) = show n ++ "*x^" ++ show k
show' k (L 0 a) = show' (k+1) a
show' k (L n a) = show' (k+1) a ++ " + " ++ show' k (C n)

instance (Num a, Eq a, Show a) => Show (Poly a) where
    show = show' 0

-- Retrieve the leading coefficient and exponent
leading :: Poly a -> (a, Integer)
leading (C n) = (n,0)
leading (L _ a) = succ <$> leading a

-- Polynomial division
polyDivMod :: (Eq a, Field a) => Poly a -> Poly a -> (Poly a, Poly a)
polyDivMod a b
    | degree a >= degree b  = let
        (m,k) = leading a
        (n,l) = leading b
        c = C (m//n) * (x^(k-l))
        (dv,md) = polyDivMod (a-c*b) b
        in (c + dv, md)
    | otherwise             = (0,a)

showDegree :: Maybe Integer -> String
showDegree (Just n) = show n
showDegree Nothing = "negative infinity"

-- Collects logs of polynomial division
polyDivModW :: (Eq a, Field a, Show a) => Poly a -> Poly a ->
    Writer [String] (Poly a, Poly a)
polyDivModW a b
    | degree a >= degree b = do
        tell . pure . concat $
            [ "We are dividing a = "
            , show a
            , " by b = "
            , show b
            , "."
            ]
        tell . pure . concat $
            [ "Since a has degree "
            , showDegree $ degree a
            , " which is larger than or equal to the degree of b, which is "
            , showDegree $ degree b
            , ", we subtract off a multiple of b."
            ]
        let (m,k) = leading a
        tell . pure . concat $
            [ "The leading term of a is "
            , show $ C m * x ^ k
            , "."
            ]
        let (n,l) = leading b
        tell . pure . concat $
            [ "The leading term of b is "
            , show $ C n * x ^ l
            , "."
            ]
        let c = C (m//n) * x ^ (k-l)
        tell . pure . concat $
            [ "We define the ratio of these leading terms as c = "
            , show c
            , "."
            ]
        tell ["Now we divide (a - b * c) by b recursively"]
        (dv, md) <- censor (("  " <>) <$>) $ polyDivModW (a - b * c) b
        tell . pure . concat $
            [ "Now we add c = "
            , show c
            , " to this quotient, to get the result that "
            , show a
            , " = ("
            , show b
            , ") * ("
            , show $ dv + c
            , ") + "
            , show md
            , "."
            ]
        pure $ (dv+c, md)
    | otherwise = do
        tell . pure . concat $
            [ "We are dividing a = "
            , show a
            , " by b = "
            , show b
            , "."
            ]
        tell . pure . concat $
            [ "Since a has degree "
            , showDegree $ degree a
            , " which is less than the degree of b, which is "
            , showDegree $ degree b
            , ", we cannot subtract off any multiples of b."
            ]
        tell . pure . concat $
            [ "Thus we get the trivial result that "
            , show a
            , " = ("
            , show b
            , ") * 0 + "
            , show a
            , "."
            ]
        pure $ (0, a)