130 lines
2.7 KiB
Haskell
130 lines
2.7 KiB
Haskell
{-# 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
|
|
|
|
|