module Chapter1 where 
{
  c0 f x = x;
  c1 f x = f x;  
  c2 f x = f (f x);

  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;

  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;

  double x = x+x;

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

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

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

}