module Chap3 where {
fact :: Integer -> Integer;
fact n = if n==0 then 1 else n*fact(n-1);

{- Preludeに定義済み
length :: [a] -> Integer;
length []     = 0;
length (x:xs) = 1 + length xs;
 -}

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);

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 ];

}