1 SequenceRecursion

-- # Software Tools for Discrete Mathematics
module Stdm03Recursion where

-- # Chapter 3.  Recursion

-- |
-- >>> factorial 5
-- 120
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

-- | Built in: length
-- >>> lengthList [1,2,3,4]
-- 4
lengthList :: [a] -> Int
lengthList [] = 0
lengthList (x : xs) = 1 + lengthList xs

-- | Bulit in: sum
-- >>> sumList [1,2,3,4]
-- 10
sumList :: (Num a) => [a] -> a
sumList [] = 0
sumList (x : xs) = x + sumList xs

-- |
-- >>> [1,2,3] ++++ [4,5,6]
-- [1,2,3,4,5,6]
(++++) :: [a] -> [a] -> [a]
[] ++++ ys = ys
xs ++++ [] = xs
(x : xs) ++++ ys = x : (xs <> ys)

-- | Built in: zip
-- >>> zipList [1,2] ['a', 'b']
-- [(1,'a'),(2,'b')]
zipList :: [a] -> [b] -> [(a, b)]
zipList [] ys = []
zipList xs [] = []
zipList (x : xs) (y : ys) = (x, y) : zipList xs ys

-- | Built in: concat
-- >>> concatList [[1,2,3],[4,5,6]]
-- [1,2,3,4,5,6]
concatList :: [[a]] -> [a]
concatList [] = []
concatList (xs : xss) = xs ++ concatList xss

-- | Built in: intercalate
-- >>>
-- 
-- intercalateList = 

-- | This is a classic elegant Haskell example.
-- >>> quickSort [34,2,13,51,23,2,490]
-- [2,2,13,23,34,51,490]
quickSort :: (Ord a) => [a] -> [a]
quickSort [] = []
quickSort (x : xs) = quickSort [y | y <- xs, y <= x] ++ [x] ++ quickSort [y | y <- xs, y > x]

-- | This is a classic elegant Haskell example.
-- >>> quickSort3 [34,2,13,51,23,2,490]
-- [2,2,13,23,34,51,490]
quickSort3 :: (Ord a) => [a] -> [a]
quickSort3 [] = []
quickSort3 (x : xs) =
  let lesser = filter (< x) xs
      greater = filter (>= x) xs
   in (quickSort3 lesser) ++ [x] ++ (quickSort3 greater)

-- | This is a classic elegant Haskell example.
-- >>> quickSort3 [34,2,13,51,23,2,490]
-- [2,2,13,23,34,51,490]
quickSort2 :: (Ord a) => [a] -> [a]
quickSort2 [] = []
quickSort2 (x : xs) = quickSort2 lesser ++ [x] ++ quickSort2 greater
  where
    lesser = [n | n <- xs, n < x]
    greater = [n | n <- xs, n >= x]

-- https://stackoverflow.com/questions/932721/efficient-heaps-in-purely-functional-languages
-- https://rosettacode.org/wiki/Sorting_algorithms/Heapsort#Haskell
-- https://gist.github.com/mmagm/2694665

-- Higher order functions that take a function as an argument:

-- | Built in: zip
-- >>> mapList (5 *) [1,2,3]
-- [5,10,15]
mapList :: (a -> b) -> [a] -> [b]
mapList f [] = []
mapList f (x : xs) = f x : mapList f xs

-- | Bulit in: elem
-- >>> elemList 4 [1,2,3,4]
-- True
elemList :: (Eq a) => a -> [a] -> Bool
elemList element [] = False
elemList element (x : xs)
  | element == x = True
  | otherwise = elemList element xs

-- | Built in: filter
-- >>> filterList even [1,2,3,4,5]
-- [2,4]
filterList :: (a -> Bool) -> [a] -> [a]
filterList f [] = []
filterList f (x : xs)
  | f x = x : filterList f xs
  | otherwise = filterList f xs

-- | Built in: find
-- >>> findList (==5) [4,5]
-- Just 5
findList :: (a -> Bool) -> [a] -> Maybe a
findList f [] = Nothing
findList f (x : xs)
  | f x = Just x
  | otherwise = findList f xs

findIndexRec :: Int -> (a -> Bool) -> [a] -> Maybe Int
findIndexRec n f [] = Nothing
findIndexRec n f (x : xs)
  | f x = Just n
  | otherwise = findIndexRec (n + 1) f xs

-- | Built in: findIndex
-- >>> findIndexList (==5) [3,4,5]
-- Just 2
findIndexList = findIndexRec 0

-- | Built in: elemIndex
-- >>> elemIndexList 5 [1,2,3,4,5]
-- Just 4
elemIndexList :: (Eq a) => a -> [a] -> Maybe Int
elemIndexList element = findIndexList (element ==)

-- | Built in: zipWidth
-- >>> zipWithList (+) [1,2,3] [4,5,6]
-- [5,7,9]
zipWithList :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWithList f [] ys = []
zipWithList f xs [] = []
zipWithList f (x : xs) (y : ys) = f x y : zipWithList f xs ys

-- | Built in: foldr
-- >>> foldrList (+) 0 [1,2,3]
-- 6
foldrList :: (a -> b -> b) -> b -> [a] -> b
foldrList f accumulator [] = accumulator
foldrList f accumulator (x : xs) = f x (foldrList f accumulator xs)

-- Some functions written in terms of foldr

-- | Built-in: sum
-- >>> sumList2 [1,2,3]
-- 6
sumList2 xs = foldr (+) 0 xs

-- | Built-in: product
-- >>> productList [1,2,3,4]
-- 24
productList xs = foldr (*) 1 xs

-- | Built-in: and
-- >>> andList [True, True, False]
-- False

-- | Built-in: and
-- >>> andList [True, True, True]
-- True
andList xs = foldr (&&) True xs

-- | Built-in: or
-- >>> orList [False, False, True]
-- True

-- | Built-in: or
-- >>> orList [False, False, False]
-- False
orList xs = foldr (||) False xs

-- |
-- >>> factorial2 5
-- 120
factorial2 n = foldr (*) 1 [1 .. n]

-- |
-- >>> firsts1 [(1,3),(2,4)]
-- [1,2]
firsts1 :: [(a, b)] -> [a]
firsts1 [] = []
firsts1 ((a, b) : ps) = a : firsts1 ps

-- | Demonstration of build in: fst
-- >>> fst (1,2)
-- 1

-- |
-- >>> firsts2 [(1,3),(2,4)]
-- [1,2]
firsts2 :: [(a, b)] -> [a]
firsts2 xs = map fst xs

-- Peano Arithmetic
-- Zero is 0
-- Succ is short for successor
-- Review this now: -- https://wiki.haskell.org/Algebraic_data_type
-- See this now, for review: ../Haskell/DataExamples.hs

data Peano = Zero | Succ Peano
  deriving (Show, Eq)

-- |
-- >>> one
-- Succ Zero
one = Succ Zero

-- |
-- >>> two
-- Succ (Succ Zero)
two = Succ one

-- |
-- >>> three
-- Succ (Succ (Succ Zero))
three = Succ two

-- |
-- >>> four
-- Succ (Succ (Succ (Succ Zero)))
four = Succ three

-- |
-- >>> five
-- Succ (Succ (Succ (Succ (Succ Zero))))
five = Succ four

-- |
-- >>> six
-- Succ (Succ (Succ (Succ (Succ (Succ Zero)))))
six = Succ five

-- | This never finishes
-- >>> take 5 infinitePeanos
-- [Zero,Succ Zero,Succ (Succ Zero),Succ (Succ (Succ Zero)),Succ (Succ (Succ (Succ Zero)))]
infinitePeanos = Zero : map Succ infinitePeanos

-- |
-- >>> decrement (Succ (Succ Zero))
-- Succ Zero

-- |
-- >>> decrement six == five
-- True
decrement :: Peano -> Peano
decrement Zero = Zero
decrement (Succ a) = a

-- |
-- >>> add (Succ (Succ Zero)) (Succ (Succ Zero))
-- Succ (Succ (Succ (Succ Zero)))

-- |
-- >>> add five one == six
-- True
add :: Peano -> Peano -> Peano
add Zero b = b
add (Succ a) b = Succ (add a b)

-- |
-- >>> sub (Succ (Succ Zero)) (Succ Zero)
-- Succ Zero

-- |
-- >>> sub two one == one
-- True
sub :: Peano -> Peano -> Peano
sub a Zero = a
sub Zero b = Zero
sub (Succ a) (Succ b) = sub a b

-- |
-- >>> equals four (Succ (Succ (Succ (Succ Zero))))
-- True

-- |
-- >>> equals four four
-- True
equals :: Peano -> Peano -> Bool
equals Zero Zero = True
equals Zero b = False
equals a Zero = False
equals (Succ a) (Succ b) = equals a b

-- |
-- >>> lt three four
-- True

-- |
-- >>> lt four three
-- False
lt :: Peano -> Peano -> Bool
lt a Zero = False
lt Zero (Succ b) = True
lt (Succ a) (Succ b) = lt a b

-- Data recursion:

-- |
-- >>> take 5 (fDatarec 1)
-- [1,1,1,1,1]
fDatarec :: a -> [a]
fDatarec x = x : fDatarec x

-- | This actually consumes memory, because it chains.
-- >>> take 5 ones
-- [1,1,1,1,1]
ones = fDatarec 1

-- | This is circular in memory, and thus much more efficient than ones!
-- >>> take 5 twos
-- [2,2,2,2,2]
twos = 2 : twos

-- |
-- >>> take 10 object
-- [1,2,3,1,2,3,1,2,3,1]
object =
  let a = 1 : b
      b = 2 : c
      c = [3] ++ a
   in a