Haskell: Generic Length/Size Calculation

length.hs

-- these imports are needed for the bottom section

import Data.Monoid
import Data.Foldable
import Data.Tree
import Control.Applicative

-- ok there's a super easy of defining length

lengthRecursiveIterator [] = 0
lengthRecursiveIterator (h:t) = 1 + length t

-- lengthRecursiveIterator ["a"] = 1

-- but that only works for lists

-- but here's a slightly more abstract way using foldr and const
-- it still only works for lists, but it will be useful later!

lengthWithFold = Prelude.foldr (const succ) 0

-- why does it work?

-- well succ is an (+ 1) function
-- succ 0 = 1
-- succ 1 = 2

-- const wraps the first parameter in a throw away function \_ -> a
-- const a b = a

-- (const succ) defines b -> a -> a
-- exactly what we need for a folder function
-- the const wraps succ, turning a -> a to b -> a -> a
-- basically one extra parameter around it
-- the intuition is that when applying const onto a function, it just gives it 
-- a extra curryable parameter on the left
-- (const succ) _ 0 = 1
-- (const succ) _ 1 = 2
-- ...
-- (const succ) throws away the left param, the left is the value of the list
-- the right is the result of the binary folder
-- so foldr on a list always goes:
{-

  lengthWithFold [a, b, c, d, e]

  <-- direction of folding
  
  where L * R = R where * is the binary folder operation
  
  [a, b, c, d, e] 0
               L  R
            L  R
         L  R  1
      L  R  2
   L  R  3
   R  4
   5
   
-}

-- what's the point of this? To show how length can use fold and const. Now we 
-- can see how to generalise length calculations to anything that is Foldable

-- we need a monoid in order to fold Foldable structures
-- the set of this monoid is the set of natural numbers N
data Measure = Measure { measure :: Int }

-- mappend allows the sizeFoldable to add up the size
instance Monoid Measure where
  mempty = Measure 0
  (Measure x) `mappend` (Measure y) = Measure (x + y) -- by default: infixl 9

-- foldMap :: Monoid m => (a -> m) -> t a -> m 
-- takes a function to a -> monoid, a foldable, and gives a monoid
-- foldMap is is an ad-hoc polymorphic function, and its implementation is 
-- different for different instances of Foldable

sizeFoldable :: Foldable t => t a -> Int
sizeFoldable = measure . (foldMap (const (Measure 1)))
-- sizeFoldable = measure . foldMap (const (Measure 1)) is also valid
-- (const (Measure 1)) wraps Measure 1 in a function, thus applied to any 
-- parameter would just return Measure 1
-- the last measure function will then take the measured integer out of the 
-- monoid

x = Node { rootLabel = "A", subForest = [] }
y = Node { rootLabel = "B", subForest = [x] }
z = Node { rootLabel = "C", subForest = [x, y] }

-- we can get the length/size of anything that is Foldable!
{-
> print $ sizeFoldable [1] -- 1
> print $ sizeFoldable (Just 1) -- 1
> print $ sizeFoldable Nothing -- 0
> print $ sizeFoldable z -- 4
-}

I think calling it a summary rather than size/length would be more appropriate. Great article anyway. :)