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)
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = (reverse xs) ++ [x]
-}
-- shunt は revの補助関数
shunt :: [a] -> [a] -> [a]
shunt ys [] = ys
shunt ys (x:xs) = shunt (x:ys) xs
rev :: [a] -> [a]
rev 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 :: Integer -> [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 ]