Functional programming

Partial application

first  = |f,x| |y| f(x,y)
second = |f,y| |x| f(x,y)

# Variadic, fix first arguments
first = |f,*a| |*b| f(*(a+b))

# Variadic, fix last arguments
last  = |f,*a| |*b| f(*(b+a))

Currying

function curry(f)
   n = f.argc()
   a = list(0..n-1)
   g = fn|x| a[n-1] = x; f(*a) end
   for i in 2..n
      g = fn|x| a[n-i] = x; g end
   end
   return g
end

function curry(f)
   n = f.argc()
   a = list(0..n-1)
   return (2..n).reduce(
      fn|x| a[n-1] = x; f(*a) end,
      |g,i| fn|x| a[n-i] = x; g end)
end

uncurry = |f| |*a| a.reduce(f,|g,x| g(x))

Fixed-point combinator

# Y combinator.
fix = |F| (|x| x(x))(|x| F(|n| x(x)(n)))


# By built-in recursion.
fix = |F| fn g|n| F(g)(n) end


# Without currying.
fix = |F| fn g|n| F(g,n) end


# With memoization.
fix = fn|F|
   m = {}
   return fn g|n|
      if n not in m then m[n] = F(g,n) end
      return m[n]
   end
end


# One argument example: factorial function.
fac = fix(|f| |n| 1 if n==0 else n*f(n-1))

# Without currying.
fac = fix(|f,n| 1 if n==0 else n*f(n-1))


# Two argument example: integer power.
pow = fix(|f| |[x,n]| 1 if n==0 else x*f([x,n-1]))

# Without currying.
pow = fix(|f,[x,n]| 1 if n==0 else x*f([x,n-1]))


for n in 0..10
   print([n,fac(n)])
end

for n in 0..10
   print([n,pow([2,n])])
end


# Variadic versions.
fix = |F| (|x| x(x))(|x| F(|*n| x(x)(*n)))
fix = |F| fn g|*n| F(g)(*n) end

fac = fix(|f| |n| 1 if n==0 else n*f(n-1))
pow = fix(|f| |x,n| 1 if n==0 else x*f(x,n-1))
print(pow(2,10))


# Variadic, without currying.
fix = |F| fn g|*n| F(*([g]+n)) end

fac = fix(|f,n| 1 if n==0 else n*f(n-1))
pow = fix(|f,x,n| 1 if n==0 else x*f(x,n-1))
print(pow(2,10))


# To be more flexible, the memoisation buffer should
# be made explicit. This allows to state the initial
# conditions in the bufffer.
fix = fn|m,F|
   return fn g|n|
      if n not in m then m[n] = F(g,n) end
      return m[n]
   end
end

fac = fix({0: 1}, |f,n| n*f(n-1))
fib = fix({1: 1, 2: 1}, |f,n| f(n-1)+f(n-2))

# Interestingly, stating the initial conditions of the
# power function becomes impossible, as there is advanced
# pattern matching on a variable involved.

# This is impossible, as [x,0] is not a pattern:
pow = fix({[x,0]: 1}, |f,[x,n]| x*f([x,n-1]))

# A somewhat ugly way to circumvent the problem:
pow = |x| fix({0: 1}, |f,n| x*f(n-1))

Composition

Function.mul = |g;f| |x| g(f(x))

compose = |*a| |x| a.rev().reduce(x,|y,f| f(y))

f = |x| 2*x
g = |x| x+1

print((g*f)(2))
print(compose(g,f)(2))