# Lista 1 programowanie funkcyjne 2020
_Paweł Dietrich_

## Zadanie 1 [2p]

- funkcja identycznościowa zdefnionwana: `fun x -> x` to funkcja polimorficzna typu `'a -> 'a`.
- `fun x -> x + 0` to także funkcja identycznościowa, ale już typu `int -> int`.
- `('a -> 'b) -> ('c -> 'a) -> ('c -> 'b)` np. `fun a b -> fun x -> a ( b ( x ) )`
- `'a -> 'b -> 'a` np. `fun a b -> a`.
- `'a -> 'a -> 'a` np. `fun a b -> if 1<0 then a else b`
- `'a` np. `Obj.magic 1`
## Zadanie 2 [1p]
Dwa sposoby

let rec f x = f x
val f : 'a -> 'b = <fun>

albo

Obj.magic
- : 'a -> 'b = <fun>

## Zadanie 3 [7p]

(* Definicje *)
let hd str = str 0
let tl str = fun idx -> str (idx+1)
let add str bias = fun idx -> bias + str idx
let map str f = fun idx -> f (str idx)
let map2 str1 str2 f = fun idx -> (f (str1 idx))(str2 idx)
let replace str n sub = fun idx -> if (idx mod n = 0) then sub else str idx
let take str n = fun idx -> str (n * idx)
let scan str f a = let rec scanrec idx = if idx<0 then a else f (scanrec (idx - 1)) (str idx) in scanrec
let tabulate s ?(l=0) r = let rec f pos = if pos > r then [] else (s pos) :: f (pos + 1) in f l

(* Testy *)
let odd_naturals x = 2*x+1
hd odd_naturals (* 1 *)
tabulate (tl odd_naturals) 5 (* [3,5,7,9,11,13] *)
let even_naturals = add odd_naturals 1
tabulate even_naturals 5 (* [2,4,6,8,10,12] *)
let double x = 2*x
tabulate (map odd_naturals double) 3 (* [2,6,10,14] *)
let sumab a b = a+b
tabulate (map2 even_naturals odd_naturals sumab) 2 (* 3 7 11 *)
let const x = 1
let alternate = (replace const 2 0)
tabulate alternate 5 (* [0,1,0,1,0,1] *)
tabulate (take alternate 2) 5 (* [0,0,0,0,0,0] *)
tabulate (scan const sumab 0) ~l:3 5 (* [4,5,6] *)

## Zadanie 4 [3p]

let ctrue a b = if a=b then a else b
let cfalse a b = if a!=b then a else b

let cbool_of_bool bool = if bool then ctrue else cfalse
let bool_of_cbool cbool = cbool false true

## Zadanie 4 [3p]

(* zadanie 4 *)
type cbool = { cbool : 'a. 'a -> 'a -> 'a };;
type cnum = { cnum : 'a. ('a -> 'a) -> 'a -> 'a };;

let ctrue  = { cbool = fun x y -> x };;
let cfalse = { cbool = fun x y -> y };;

let cand ca cb =
  ca.cbool (cb.cbool ctrue cfalse) cfalse;;
let cor ca cb =
  ca.cbool ctrue (cb.cbool ctrue cfalse);;
let cbool_of_bool l =
  if l then ctrue
  else cfalse;;
let bool_of_cbool f =
  (f.cbool 1 0) = 1;;

  let ctrue tt ff = tt;;
  let cfalse tt ff = ff;;

  let cand a b tt ff = a (b tt ff) ff;;

  let cor a b tt ff = a tt (b tt ff);;

  let cbool_of_bool b tt ff = if b then tt else ff;;

  let bool_of_cbool c = c true false;;

## Zadanie 5 [3p]

let zero f x = x;;
let succ t f x = f (t f x);;

let rec cnum_of_int i f x = if i = 0 then x else f (cnum_of_int (i-1) f x);;

let rec cnum_of_int i =
    if i = 0 then zero else succ (cnum_of_int (i-1) f x);; 

(* (Int.add 1)  *)
let int_of_cnum t = t (fun x->x+1) 0;;

let add t1 t2 f x = t1 f (t2 f x);;

let rec mul t1 t2 ?(ind=0) f x = if (int_of_cnum t1) = ind then x else
  mul t1 t2 ~ind:(ind+1) f (t2 f x);;

let is_zero t = t (fun x->(x+1)) 0 = 0;;

Oskar Fiuk

let zero f x = x
let succ n f x = f (n f x)
let add n m f x = n f (m f x)
let mul n m f = n (m f)
let is_zero n = n (cand cfalse) ctrue
let rec cnum_of_int x = if x = 0 then zero else succ (cnum_of_int (x - 1))
let int_of_cnum n = n (( + ) 1) 0

## Zadanie 6 [4p]

type cnum = { cnum : 'a. ('a -> 'a) -> 'a -> 'a }

let zero = {cnum = fun f x -> x};;

let bar = { cnum = 7 }
(* bar : { cnum : int } *)

let succ (n: cnum) = {cnum = fun g x -> g (n.cnum g x)};;

let add (m: cnum) (n: cnum) = { cnum = fun f x -> m.cnum f (n.cnum f x) };;

let mul (m: cnum) (n: cnum) = {cnum = fun f x -> m.cnum (n.cnum f) x};;

let is_zero (n: cnum) = {cbool = fun x y -> n.cnum (fun x -> y) x};;

let rec cnum_of_int (n: int) = 
  if n = 0 then zero else succ (cnum_of_int (n-1));;

let int_of_cnum (n: cnum) =
  n.cnum (fun x -> x + 1) 0;;