module Chap3 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の (++)演算子と 同じ
append :: [a] -> [a] -> [a]
append [] ys = ys
append (x:xs) ys = x : (append xs ys)
{- Preludeに定義済み
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = append (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 = append (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 = [ append p [n] | p<-queens (m-1), n<-[1..8], safe p n ]