most of Data.List's functions without recursion

gistfile1.hs

-- Church encoded constructors
cons = (Data.constructor 0 (List _))
nil  = (Data.constructor 1 (List _))

-- Returns the first element of a church-encoded list
head          = (cons?,nil?)
    cons? h t = h
    nil?      = nil

-- Returns the tail of a church-encoded list
tail list cons nil = (list cons? nil? skip)
    skip  h t      = t
    cons? h t      = (cons_or_skip -> (cons_or_skip h (t cons)))
    nil?           = (cons_or_skip -> nil)

-- Haskell-like right fold over a church-list
foldr cons nil list = (list cons nil)

-- Haskell-like left fold over a church-list
foldl cons nil list = (list cons? nil? nil)
    cons? h t accum = (t (cons accum h))
    nil?      accum = accum

-- Applies a function to each element of a list
map fn list cons = (list (comp cons fn))

-- Builds an `imap` function given a specific Nat implementation.
imap$ succ zero f list cons nil = (list cons? nil? zero)
    cons? head tail i           = (cons (f i head) (tail (succ i)))
    nil? l                      = nil

-- Like map, but first argument of fn is the elements's index as a Nat.
imap = (imap$ succ zero)

-- Alias to imap (TODO: remove)
map_indexed = imap

-- Filters each element of a list
filter cond list cons nil = (list cons? nil?)
    cons? h t             = (cond h (cons h t) t)
    nil?                  = nil

-- Reverses a list
reverse list cons nil = (foldl (flip cons) nil list)

-- Like Haskell's scan, except returning the tail
scantail c n list cons_ nil_ = (list cons? nil? nil)
    cons? h t x              = (cons_ (c h x) (t (c h x)))
    nil? x                   = nil_

-- Haskell-like scan over a list
scan c n list = (cons n (scantail c n list))

-- Inserts element at the end of a list
push element = (foldr cons (cons element nil))

-- Number of elements in a list
length = (flip comp const)

-- Drops n elements from a list
drop n = (n tail)

-- returns the same list, but dropping the last element.
init list cons nil = (list cons? (res del -> del) (res -> res) nil)
    cons? h t      = (t res? del?)
        res? r     = (res del -> (res (cons h r)))
        del?       = (res del -> (res nil))

-- Takes the first n elements from a list
take n list cons nil = (list cons? nil? (n Succ Zero))
    cons? h t n      = (n Succ? Zero?)
        Succ? pred   = (cons h (t pred))
        Zero?        = nil
    nil? n           = nil

-- Last element of a list
last = (comp head reverse)

-- Returns true if list is empty
empty = (foldr (h t -> false) true)

-- Concatenates 2 lists. This works like Haskell's (++), not `concat`.
concat a b cons nil = (a cons (b cons nil))

-- Flattens a list of list into a list. Works like Haskell's `concat`.
flatten = (foldr concat nil)

-- Composes a list of functions; rightmost function is executed first.
compose = (foldr comp id)

-- Composes a list of functions; leftmost function is executed first.
do = (comp compose reverse)

-- The dreaded hyperfunctional, recursion-less zip_with.
zip_with f a b = ((left a) (right f b))
    left       = (foldr (x xs cont -> (cont x xs)) (const nil))
    right      = (f -> (foldr (y ys x cont -> (cons (f x y) (cont ys))) (const (const nil))))

-- Iterates over two lists in parallel, returning a list of pairs.
zip = (zip_with pair)

-- Applies list of functions to list of elements in parallel (zipp = zip + app).
zipp = (zip_with id)