lambdas, pattern matching and binding symbols to values are essential primitive operations.

A mapping

A function is another name for a mapping. A function f maps (transforms) Xs to Ys.

Same input, same output. Always. This is, in part, how Referential transparency could be accomplished.

A lookup table

Given the definitions above, a function could be thought as a lookup table.

val day = fn 1 => "Monday"
           | 2 => "Tuesday"
           | 3 => "Wednesday"
           | 4 => "Thursday"
           | 5 => "Friday"
           | 6 => "Saturday"
           | 7 => "Sunday"
cost x = case x of
     "oranges"   ->  5
     "newspaper" ->  8
     "apples"    ->  2

Multiple clauses

In some languages a function might have multiple clauses (and multiple bodies).


cost(oranges)   -> 5;
cost(newspaper) -> 8;
cost(apples)    -> 2;
cost(pears)     -> 9;
cost(milk)      -> 7.

A constant function

An identity function

Single argument and currying

in some languages a function could take exactly one argument (but this argument is a pattern, like n-tuple)

curry transforms a fiven function into its curried form

val curry = fn f => fn x => fn y => f (x, y)

uncurry transforms a curried function into tuple-form.

val uncurry = fn f => fn (x, y) => f x y

Pattern matching

for functions it constrains the type or value of the parameter by requiring the parameter to match a given pattern


lambdas of different number of arguments in some languages could be bound to the same symbol.

it is a standard idiom in Erlang, Clojure and others to use functions of different arity as auxiliary helper functions

sum(Xs) -> sum(Xs, 0).

sum([], A) -> A;
sum([H|T], A) -> sum(T, H+A).

Static typing

datatype t = A | B

fun f x y = 
    case (x, y) of
         (A, A)  => "a, a"
       | (A, B)  => "a, b"
       | (B, A)  => "b, a"
       | (B, B)  => "b, b"

syntactic sugar, similar to multimethods

fun f (A, A)  => "a, a"
    | (A, B)  => "a, b"
    | (B, A)  => "b, a"
    | (B, B)  => "b, b"

Signatures and multi-methods

A set of functions with the same name (binding) but different type-signatures (clauses) is also called multimethods.

Common Lisp (via CLOS), Clojure and Julia have multimethods.

Classic functions to meditate upon

The point is to realize how the truly declarative style in Haskell (describe what shall be done instead of how to do it) differs from imperative style in Scheme (do this then that - an ordered sequence of steps). This is the power of Pattern Matching - it makes code to look less imperative, encapsulating explicit desctucturing and binding.

Erlang, which is also relies heavily on pattern matching is closer than Scheme to the declarative style of Haskell.

We will use more esoteric notation with explicit lambdas for Scheme and Haskell to respect the tradition and to illustrate all the subtleties (and standard syntax for all other languages).

Haskell, being a "lazy language", uses Normal order of evaluation. Scheme uses Applicative order with explicit lazyness (via macros or the delay special form).

map, foldr, foldl, See also Folds

partially - partial application

See also Bootsrapping Folds

Last modified 4 years ago Last modified on Mar 13, 2017, 8:49:59 PM
Note: See TracWiki for help on using the wiki.