module fold

import StdEnv

:: List a = Nil | Cons a (List a)

(~>) infixr 4 :: (a (List a) -> List a)
(~>) = Cons

foldr :: (a -> b -> b) b (List a) -> b
foldr f x Nil = x
foldr f x (Cons a l) = f a (foldr f x l)

map :: (a -> b) -> (List a) -> (List b)
map f = foldr (Cons o f) Nil

sum = foldr (+) zero
product = foldr (*) one

any = foldr (||) False
all = foldr (&&) True

copy = foldr Cons Nil
append a b = foldr Cons b a
length = foldr (\_ n -> n + 1) 0

:: Tree a = Node a (List (Tree a))

(@) infixr 4 :: (a (List (Tree a)) -> Tree a)
(@) = Node

foldtree :: (a -> b -> c) (b -> c -> b) b (Tree a) -> c
foldtree f g a (Node l ts) = f l (foldtree` f g a ts)
where
    //foldtree` :: (a -> b -> c) (c -> b -> b) b (List (Tree a)) -> b ??
    foldtree` f g a (Cons t r) = g (foldtree f g a t) (foldtree` f g a r)
    foldtree` f g a Nil = a

Start = map ((*)2) (5 ~> 10 ~> Nil)