module Chap2 where

fact :: Integer -> Integer
fact n = if n == 0 then 1 else n * fact (n - 1)

myLength :: [a] -> Integer
myLength []     = 0
myLength (x:xs) = 1 + myLength xs

{- -- Prelude に定義ずみ
(++)           :: [a] -> [a] -> [a]
[] ++ ys      = ys
(x:xs) ++ ys  = x : (xs ++ ys)
 -}
rev0   :: [a] -> [a]
rev0 []     = []
rev0 (x:xs) = (rev0 xs) ++ [x]


-- shunt は revの補助関数
shunt          :: [a] -> [a] -> [a]
shunt ys []     = ys
shunt ys (x:xs) = shunt (x:ys) xs
{- -- Prelude に定義ずみ
reverse   :: [a] -> [a]
reverse xs = shunt [] xs
-}

{- Preludeに定義済み
zip :: [a] -> [b] -> [(a,b)]
zip (a:as) (b:bs) = (a,b) : zip as bs
zip _       _     = []
 -}

pow4 x = let { y = x * x } in y * y
{- Preludeに定義済み
head ys = let { (x:xs) = ys } in x

repeat  :: a -> [a]
repeat x = let { xs = x:xs } in xs
-}

data Direction = Up | Down | Left | Right

data Tree a = Branch (Tree a) a (Tree a) | Empty

from :: Integer -> [Integer]
from n = n : from (n + 1)

{- Preludeに定義済み
take :: Int -> [a] -> [a]
take 0 _      = []
take _ []     = []
take n (x:xs) = x : take (n - 1) xs

-- primes （問 3.9.3）に使用するかも

filter p []     = []
filter p (x:xs) = if p x then x : filter p xs else filter p xs

map f []     = []
map f (x:xs) = f x : map f xs

iterate f a = a : iterate f (f a)
-}

unit :: a -> [a]
unit a = [a]

bind :: [a] -> (a -> [b]) -> [b]
bind []     _ = []
bind (x:xs) f = (f x) ++ (bind xs f)

qsort []     = []
qsort (x:xs) = qsort [ y | y <- xs, y < x] ++ x : qsort [ y | y <- xs, y >= x]

safe p n  = all not [ check (i, j) (1 + length p, n) | (i, j) <- zip [1..] p ]
check (i,j) (m,n) = j == n || (i + j == m + n) || (i - j == m - n)

{- Preludeに定義済み
all               :: (a -> Bool) -> [a] -> Bool
all p []           = True
all p (x:xs)       = if p x then all p xs else False
-}

queens 0  = [[]]
queens m  = [ p ++ [n] | p <- queens (m - 1), n <- [1..8], safe p n ]