foldr2ways.md

foldr written the normal way and as the dual of unfoldr

The following code was inspired by Kwang's Haskell Blog post titled unfold and fold.

module Main where

import Prelude hiding (foldr)
import Data.Function ((&))

list :: [Int]
list = [1, 2, 3, 4]

main :: IO ()
main = do
  let s = list & foldr (-) 0
  print s
  let s' = list & foldr' (maybe 0 $ uncurry (-))
  print s'

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f i []      = i
foldr f i (x:xs)  = x `f` foldr f i xs

foldr' :: (Maybe (a, b) -> b) -> [a] -> b
foldr' g []       = g Nothing
foldr' g (x:xs)   = g $ Just (x, foldr' g xs)

Interesting note: The initial value that's passed to foldr gets put into the function passed to foldr' during the Type Isomorphism step (in Kwang's blog post) that uses the following isomorphism rule:

((a -> c), (b -> c)) ~= Either a b -> c

It's at this point, we lose the constant, () -> b, in the second position of the tuple:

(((a, b) → b), (() -> b)) → ([a] → b)
                \------/

and after applying the substitution from the above rule, we get:

(Either (a, b) () → b) → ([a] → b)
 \------------------/

which absorbs the constant into the function, Either (a, b) () -> b.