This article first from my blog eczn. Making. IO/blog/cc2509… Here is the transcript:
Write an article about functions and first-class citizens, because I found something interesting.
I wanted to implement tuples as data structures in my functional dialect interpreter, but I didn’t have any direction, so I looked at the syntax of Scheme, looked at Wiki, and found myself implementing Pair in Lisp.
Lisp, you’ve probably heard of it, we don’t need it here, but what’s a Pair, it’s actually a very simple data structure, something like this, in TyepScript:
// Create a pair
function cons(l: number, r: number) {
return [l, r]
}
// Take the left side of the pair
function car(my_pair: number[]) {
return my_pair[0];
}
// Remove the right side
function cdr(my_pair: number[]) {
return my_pair[1];
}
Copy the codeAs an aside, the name of the scheme function that creates a pair is cons, as are its two operations, CAR and CDR, so this article will use that name as well.
A data structure like this, called a Pair, exists in many js libraries. For example, react. useState returns a Pair with values on the left and a dispatcher on the right.
But what we’re talking about here is using arrays, so is there another way to implement this data structure? Of course, the answer is yes. The following sections will show how to implement such data structures only using functions, and how to implement linked lists and binary trees only using functions.
The functional implementation of Pair
Since I wanted to add the pair type to the interpreter of a functional dialect I wrote, I looked at the functional implementation of pair, as follows:
;; Code excerpted from Wiki
;; https://en.wikipedia.org/wiki/Cons
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
(define (cdr z)
(z (lambda (p q) q)))
Copy the codeTypeScript translation looks like this:
// Let's define the data structure type Pair as a function
type Pair = Function;
// Create a cons
function cons(x: number, y: number) :Pair {
return (how_to_do_it: Function) = > {
returnhow_to_do_it(x, y); }}// Fetch the pair lvalue
function car(pair: Pair) {
return pair((l, r) = > l)
}
// Fetch the rvalue of the pair
function cdr(pair: Pair) {
return pair((l, r) = > r)
}
const xy = cons(1.2);
// Calling cons returns a function
const x = car(xy);
/ / = > 1
const y = cdr(xy);
/ / = > 2
Copy the codeThe above code perfectly embodies the concept of functions as first-class citizens, because we only use functions to implement data structures, which is the meaning behind first-class citizens.
The challenge: Functional linked lists
Now, we have Pair, which has two values, and in addition, these two values are also ordered, can it be used to construct a linked list?
Sure, because we’re not taking into account what the two values are. An lvalue or rvalue in a Pair can be either a number or another Pair. That is, pairs can be nested within pairs, from which linked lists can be defined recursively:
Pair (number, number | Pair | null) if and only if the right value is null, we think the list in the end
From the above discussion, it is easy to recursively construct linked lists using pairs; that is, lists can be implemented using functions alone.
If you don’t understand what it means to recursively define a linked list, you can look at the following code to see what it means:
cons(1, cons(2, cons(3))) 1 -> 2 -> 3
Based on the discussion above, the TypeScript implementation is as follows:
type Pair = Function;
function cons(x: number, y? :number | Pair) :Pair {
return (how_to_do_it: Function) = > {
returnhow_to_do_it(x, y); }}function car(pair: Pair) {
return pair((l, r) = > l)
}
function cdr(pair: Pair) {
return pair((l, r) = > r)
}
// Retrieve the NTH item in the list
function nth(pair: Pair, n: number) {
if (n === 0) {
return car(pair);
} else {
return nth(cdr(pair), n - 1); }}const lst = cons(1, cons(2, cons(3)))
// 1 -> 2 -> 3
const number = nth(lst, 0);
/ / = > 1
Copy the codeAs you can see, cons y can be empty or pair, so there’s a recursion, so it’s easier to do it recursively when you’re fetching lists.
The challenge: functional binary trees
The above discussion has implemented linked lists, and one of the most special aspects of a list is references. If the references become two, the list can be generalized to a binary tree.
Here is my implementation:
// In languages where functions are first-class citizens,
// A function is a data type/structure
type Tree = Function;
// Function binary tree
// If no type is specified, the value stored in the tree is considered to be a number;
function Tree<T = number> (v: T, l? : Tree, r? : Tree) :Tree {
return (how_to_do_it: Function) = > {
returnhow_to_do_it(v, l, r); }}// take the left subtree
function lchild(tree: Tree) {
return tree((v, l, r) = > l);
}
// take the right subtree
function rchild(tree: Tree) {
return tree((v, l, r) = > r);
}
/ / value
function valOf(tree: Tree) {
return tree((v, l, r) = > v);
}
// Preorder traversal of a functional binary tree
function traversal(t? : Tree) {
if(! t)return;
const l = lchild(t);
const r = rchild(t);
const v = valOf(t);
console.log(v);
traversal(l);
traversal(r);
}
// Create a tree...
// Although a bit devious...
const t =
Tree(1,
Tree(2,
Tree(3), Tree(4)), Tree(5, Tree(6)))
// The structure is as follows:
/ / 1
/ / / /
/ / 2, 5
/ / / / /
/ / 3, 4, 6
// Iterate the results first
traversal(t);
// => Print: 123456
Copy the codeThe above code realizes the representation of binary tree, and gives the way of sequential traversal of binary tree.
So, what is a function?
I don’t know 233 yet, but it’s true that learning functional languages on and off is different every time.
As you can see from the above illustration, the fact that functions are first-class citizens means that functions can implement other things in a programming language, such as data structures.
This part involves Lambda Calculus, which I haven’t learned much about… I’m not expanding.