Aunque parezca que un lenguaje como Haskell tiene muchos objetos y construcciones diferentes, podemos expresarlos todos en términos de funciones.
let
n = 10
f x = x+1
in
f n
-- Una variable por let =>
let
n = 10
in
let
f x = x+1
in
f n
-- Reescribe f como lambda =>
let
n = 10
in
let
f = \x -> x+1
in
f n
-- Reescribe el let interno como lambda =>
let
n = 10
in
(\f -> f n) (\x -> x+1)
-- Reescribe el let externo como lambda =>
( \n -> ((\f -> f n) ( \x -> x+1 )) ) 10
Entonces, las variables y las expresiones let son solo azúcar sintáctico para las expresiones lambda.
tp = (1,"2",[3])
La notación de tupla es azúcar sintáctica para una aplicación de función:
tp = mkTup 1 "2" [3]
La función de construcción de tuplas se puede definir de nuevo simplemente usando lambdas:
mkTup = \x y z -> \t -> t x y z
Lo mismo ocurre con las funciones de acceso a la tupla:
fst tp = tp (\x y z -> x)
snd tp = tp (\x y z -> y)
Las listas se pueden definir en términos de listas vacías [] y la operación de contras (:).
ls = [1,2,3]
Se puede escribir con : y [] =>
ls = 1 : 2 : 3 : []
O usando cons =>
ls = cons 1 (cons 2 (cons 3 []))
Podemos definir cons usando solo funciones lambda como
cons = \x xs ->
\c -> c x xs
Así
ls = cons 1 (...)
= \c -> c 1 (...)
También podemos definir head y tail usando solo lambdas:
head ls = ls (\x y -> x)
tail ls = ls (\x y -> y)
Podemos definir la lista vacía de la siguiente manera:
[] = \f -> true
Las definiciones de verdadero y falso se dan a continuación bajo Booleanos.
Luego podemos verificar si una lista está vacía o no:
isEmpty lst = lst (\x xs -> false)
Una lista no vacía siempre se define como:
lst = x: xs
que con nuestra definición de (:) es
lst = (\x xs -> \c -> c x xs) x xs
= \c -> c x xs
Así que :
isEmpty lst
= isEmpty (\c -> c x xs)
= (\c -> c x xs) (\x xs -> false)
= false
isEmpty []
= isEmpty (\f -> true)
= (\f->true) (\x xs -> false)
= true
Ahora que podemos probar la lista vacía, podemos definir recursiones en listas como foldl, map, etc.
foldl f acc lst =
if isEmpty lst
then acc
else foldl f (f (head lst) acc) (tail lst)
y
map f lst =
let
map' f lst lst' = if isEmpty lst then (reverse lst') else map' f (tail lst) (head lst: lst')
in
map' f lst []
con
reverse lst = (foldl (\acc elt -> (elt:acc)) [] lst
Las definiciones de foldl y map usan una expresión if-then-else que se define a posteriormente en condicionales.
Concatenación de lista : (++) lst1 lst2 = foldl (\acc elt -> (elt:acc)) lst2 (reverse lst1)
Para calcular la longitud de una lista necesitamos números enteros, se definen a continuación.
length lst = foldl calc_length 0 lst
where
calc_length _ len = inc len
Hemos utilizado condicionales en las expresiones anteriores:
if cond then if_true_exp else if_false_exp
Aquí cond es una expresión que devuelve verdadero o falso, que se definen a continuación.
Podemos escribir la cláusula if-then-else como una función pura:
ifthenelse cond if_true_exp if_false_exp
Para evaluar la condición necesitamos definir booleanos:
true = \x y -> x
false = \x y -> y
Con esta definición, el if-then-else se convierte simplemente
ifthenelse cond if_true_exp if_false_exp = cond if_true_exp if_false_exp
Usando ifthenelse podemos definir y, o y no:
and x y = ifthenelse x (ifthenelse y true) false
or x y = ifthenelse x true (ifthenelse y true false)
not x = ifthenelse x false true
Observamos que para probar la igualdad de los booleanos podemos usar xnor y, por supuesto, podemos definir xor en términos de y, o y no:
xor x y = (x or y) and (not x or not y)
xnor x y = not (xor x y)
Enteros firmados
Definimos un entero como una lista de valores booleanos, en codificación de termómetro, y con las siguientes definiciones:
Definimos usigned 0 como una lista de 1 elemento que contiene false. Para obtener enteros con signo, simplemente definimos el primer bit de la lista como el bit de signo. Definimos versiones firmadas y sin firmar de 0:
u0 = false:[]
0 = +0 = true:u0
-0 = false:u0
Por conveniencia definimos también:
isPos n = head n
isNeg n = not (head n)
isZero n = not (head (tail n))
sign n = head n
La definición de 0 facilita la igualdad de enteros (==):
(==) n1 n2 = let
s1 = head n1
s2 = head n2
b1 = head (tail n1)
b2 = head (tail n2)
if (xnor s1 s2) then
if (and (not b1) (not b2))
then true
else
if (and b1 b2)
then (==) (s1:(tail n1)) (s2:(tail n2))
else false
else false
También podemos definir fácilmente la negación:
neg n = (not (head n)):(tail n)
Por conveniencia definimos también definimos operaciones de incremento y decremento:
inc n = if isPos n then true:true:(tail n) else if isZero n then 1 else false:(tail (tail n))
dec n = if isZero n then -1 else if isNeg n then false:true:(tail n) n else true:(tail (tail n))
La adición general es bastante fácil:
add n1 n2 = foldl add_if_true n1 n2
where
add_if_true elt n1 = if elt then true:n1 else n1
Del mismo modo, la resta también es sencilla:
sub n1 n2 = foldl sub_if_true n1 n2
where
sub_if_true elt n1 = of elt then (tail n1) else n1
Una forma sencilla de definir la multiplicación es definiendo las operaciones de replicación y suma:
replicate n m =
let
repl n m lst = if n==0 then lst else repl (dec n) m (m:lst)
in
repl n m []
sum lst = foldl add 0 lst
Entonces la multiplicación simplemente se convierte en
mult n m = sum (replicate n m)
De manera similar, se pueden definir la división y el módulo de enteros.
Observamos que los flotantes y los caracteres utilizan una representación de números enteros, y las cadenas son simplemente listas de caracteres. Entonces ahora tenemos un lenguaje que puede manipular listas y tuplas de enteros, flotantes, caracteres y cadenas.
