{-# LANGUAGE NoImplicitPrelude #-}

import Prelude hiding (map, filter, foldl, foldr, takeWhile)
import Debug.Trace

-- Base

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x : xs) = f x : map f xs

filter :: (a -> Bool) -> [a] -> [a]
filter f [] = []
filter f (x : xs) = if f x then x : filter f xs else filter f xs

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f e [] = e
foldl f e (x : xs) = foldl f (f e x) xs

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

inserts :: a -> [a] -> [[a]]
inserts x [] = [[x]]
inserts x (y : ys) = (x : y : ys) : map (y :) (inserts x ys)

perms1 :: [a] -> [[a]]
perms1 [] = [[]]
perms1 (x : xs) = [zs | ys <- perms1 xs, zs <- inserts x ys]

-- Exercise 1.2

uncons :: [a] -> Maybe (a, [a])
uncons [] = Nothing
uncons (hd : tl) = Just (hd, tl)

-- Exercise 1.3

wrap :: a -> [a]
wrap x = [x]

unwrap :: [a] -> a
unwrap [x] = x

single :: [a] -> Bool
single [x] = True
single _ = False

-- Exercise 1.4

reverse :: [a] -> [a]
reverse = foldl (\a x -> x : a) []

-- Exercise 1.5

map2 :: (a -> b) -> [a] -> [b]
map2 f = foldr (\x a -> f x : a) []

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 f = foldr (\x a -> if f x then x : a else a) []

-- Exercise 1.6

composed :: (a -> b -> b) -> (a -> Bool) -> b -> [a] -> b
composed f p e = foldr f e . filter p

composed2 :: (a -> b -> b) -> (a -> Bool) -> b -> [a] -> b
composed2 f p = foldr (\x a -> if p x then f x a else a)

-- Exercise 1.7

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile f = foldr (\x a -> if f x then x : a else []) []

-- Exercise 1.8

dropWhileEnd :: Eq a => (a -> Bool) -> [a] -> [a]
dropWhileEnd f = foldr (\x a -> if f x && a == [] then [] else x : a) []

-- Exercise 1.9
-- This implementation is insanely slow because both `init` and `last` are O(n)

-- Exercise 1.10
-- e is the identity, op is associative

-- Exercise 1.11

integer :: [Int] -> Int
integer = foldl (\a x -> 10 * a + x) 0

fraction :: [Int] -> Double
fraction = (/ 10) . foldr (\x a -> fromIntegral x + a / 10) 0

-- Exercise 1.12
-- Fuck this

-- Exercise 1.13

apply :: Int -> (a -> a) -> a -> a
apply 0 f x = x
apply n f x = apply (n - 1) f (f x)

-- Exercise 1.14

-- inserts2 :: Show a => a -> [a] -> [[a]]
inserts2 n = foldr (\x (a, b) -> (trace ("{"++show a++","++show b++"}") (x : a), b)) ([], [])

-- 1 [2,3,4]
-- 
-- 1:2:3:4
-- map (2:) (inserts 1 [3,4])
--   2: 1:3:4
--   2: map (3:) (inserts 1 [4])
--     2:3: 1:4
--     2:3: map (4:) (inserts 1 [])
--       2:3:4: 1

-- Exercise 1.15

remove :: Eq a => a -> [a] -> [a]
remove x ys = filter (/= x) ys

perms3 :: Eq a => [a] -> [[a]]
perms3 [] = [[]]
perms3 xs = [x : ys | x <- xs, ys <- perms3 (remove x xs)]

-- Exercise 1.16