Former article juejin. Cn/post / 694082…
Day 4: Data and functions
Student: Fong, what’s on today?
Fang: What did you learn in the first three days
Student: Yes
- Recursion is not scary. Some languages are not optimized because they do not encourage recursion, not because recursion is slow.
- There is a special form of recursion called tail recursion, which avoids bursting the stack
- Functions can be single parameter form, can add type
- And a little Haskell knowledge, for example
$symbol
Fang: Well, you see, we haven’t learned much
Student:… You say so…
Fang: Today we are going to look at slightly more complex structures. Previously we only dealt with numbers, strings and functions. Although arrays are used, they are only used in JS, not Haskell.
Student: Wait, I have a question, what do you mean when you say a function is data?
Fang: I’ll tell you the answer in this lesson.
Student: Interesting. Let’s do it.
First, let’s discuss the simplest compound data structure: (a, b), for example:
- We can use (4, 2) to represent a point of x coordinate 4 and y coordinate 2;
- We can use (2, 4) to represent a point of 2 x and 4 y;
- You can use “Fang “,” Ying Hang “to denote family name and given name.
- You can use (1, “one”) to represent the relation between 1 and “one”;
This data can have only two elements, which can be of different types. Such data structures are called binary or ordered pairs, or pairs. Note that this is an abstract data structure and is not limited to Haskell.
Student: There’s no such data structure in JS, but it looks like an array of fixed length 2?
Fang: You can understand it this way.
Student: What apis does a pair have?
Only two apis: First and second
// JS style API const pair = createPair(1, 2) first(pair) // Get 1 second(pair) 2) FST pair -- that's 1. SND pair -- that's 2Copy the codeFang: What would you do if I asked you to implement pair with JS?
Student: How about this:
createPair = (a, b) => [a, b]
first = pair => pair[0]
second = pair => pair[1]
Copy the codeFang: Ok, let me give you another way to see if you can understand it:
createPair = (a, b) =>
n =>
n === 0 ? a : b
first = pair => pair(0)
second = pair => pair(1)
Copy the codeStudent: What’s this? Does your createPair return a function?
Fang: well.
Student: The pair function returns a if it receives 0 and b if it receives anything else?
Fang: well.
Student: Wait, I haven’t accepted pair as a function yet… Isn’t it an array or an object?
Fang: That’s your preconception. Do you think functions are functions and data are data?
Student: Isn’t it?
Fang: Take a closer look at these three codes:
array[0]
object[0]
fn(0)
Copy the codeIs it passing the argument 0 to three things, why can’t they all be functions?
Student: Wait a minute, I think I got it when you said that! Array [0] can indeed be viewed as array(0), so array is a function. What about array.length? Does our function support adding attributes?
Fang: No, just think of array.length as array(‘length’)
Student: Well, array, object, and FN are essentially the same.
Fang: I think so.
Student: That’s interesting
Fong: The createPair code I just created is actually left a hand, you can see if you can read it:
createPair = (a, b) => fn => fn(a, b)
first = pair => pair((x,y) => x)
second = pair => pair((x,y) => y)
Copy the codeStudent: Let me have a look first. (Two minutes later) Boy,
- CreatePair accepts a, b, fn and then calls fn(a, b), seemingly doing nothing
- But when you call first(pair), fn is assigned (x, y)=> x
- And then you plug a and b into x and y, and you get a
- So first(pair) is going to get a
- Similarly, second is going to get b
I wouldn’t have thought of it myself, and my colleagues wouldn’t have understood it either
Fang: Good analysis, as long as the use of “substitution” easy to understand, otherwise very difficult to understand.
Student: “substitution method” is really good. At first I wanted to read the code directly, but I found it didn’t work. Later, I wrote it on paper by substitution:
pair = createPair(1, 2)
= fn => fn(1, 2)
first(pair)
= first(pair)
= pair ((x,y) => x)
= (fn => fn(1, 2)) ((x,y) => x)
= ((x,y) => x) (1, 2)
= 1
Copy the codeSo we have finished our first lesson: we can express a pair with a function. And again, we’re using substitution. Note, however, that this is not necessarily how createPair, First, and Second are implemented in Haskell; we only write this code for learning purposes.
Student: NOW I kind of understand what you said at the beginning: “It’s not going to help me in my day job, but it’s going to help me understand the code in a different way.”
Next, we’ll start with the second kind of data structure, a list, which you can also call an array. Again, this is an abstract data structure, not limited to one language. For example:
- [] indicates an empty list
- [1, 2, 3, 4, 5] represents five numbers
- [“hi”, “hi”] represents two strings
- [1, “hi”] contains different types of elements, and we’re not talking about this kind of list
The list is ordered, and the API has:
- Head List – Gets the first element
- Last list – Gets the last element
- Tail list – Gets elements other than the first one
- Get n list – Get the NTH element
Can you implement a createList with JS?
Student: That’s not easy, it’s just an array of JS:
const createList = (... Args) => [...args] const list = createList(1,2,3,4,5) const head = list => list[0] const tail = ([first, ...rest]) => rest const last = list => list[list.length - 1] const get = (n, list) => list[n]Copy the codeIs that ok?
Fang: Yes, but you are using too many built-in JS functions. Look at this:
const cp = createPair const list = cp(1, cp(2, cp(3, cp(4, cp(5, Null))))) const head = list => list((x,y) => x) // head and first equivalent const tail = list => list((x,y) => y) // tail and tail Const last = list => tail(list) === null? head(list) : last(tail(list)) const get = (n, list) => n === 1 ? head(list) : get(n-1, tail(list))Copy the codeStudent: Your list is a binary, and the second item of a binary could be another binary?
Fang: Well, each tuple is actually (data, next), where data refers to the data and next refers to the next item. For your convenience, I will use Figure 1 to show it:
// Figure 1 list -> (1, ↓) (2, ↓) (3, ↓) (4, ↓) (5, empty)Copy the codeStudent: This is a linked list in a data structure. But why not use continuous memory representation… Continuous memory is more efficient isn’t it?
F: The continuous memory “insert data” and “expand” is extremely inefficient, isn’t it? It’s just that index is more efficient. Also, I didn’t say the memory form of the list… It can be sequentially stored, it can be chained, I don’t care.
Student: Don’t care about memory?
Fang: That’s right. You should try to think outside of “memory,” which is what you used to think of data structures as, for example, arrays as contiguous chunks of memory, and objects as random bits of data stored in heap memory.
Student: I guess so. I didn’t even notice until you told me.
Fang: From now on, let’s not talk about memory, ok?
Student: Ok, I’ll try. However,cp(1,cp(2… Such code is cumbersome to write
Fang: We just need to add grammar sugar:
let list = 1:2:3:4:5:[]
Copy the codeLook from right to left:
5: [] - equivalent to the cp (5, null), get [5] 4:5: [] - equivalent to the cp (4 cp (5, null)), Get [4, 5] 3:4:5: [] - get 2:3:4, three, four, five, five: [] - get 5-tetrafluorobenzoic [2] syntactic sugar for 1:2:3:4:5: [] - get [1, 2, 3, 4, 5]Copy the codeIt even provides the way you want to write it:
Let the list = [1, 2, 3, 4, 5]Copy the codeRemember, however, that it does not mean contiguous memory [1], but rather something like tuples [2] within tuples (see Figure 1). As for whether memory is contiguous or not, the answer is either contiguous or discontiguous, and we don’t care at this point.
Student: I get the point, but the code looks a little silly
Fang: You write code like this every day, remember?
Student: No, it’s not possible
Fang: Let me ask you, do you use React recently?
Student: Yeah
Fang: Do you write code like this every day:
Return (<div class="wrapper"> <div class="box"> <span class="title"> title </span> </div> </div>)Copy the codeStudent: Well, it’s good
Is the above code equivalent to
const h = React.createElement
return (
h('div', {className:'wrapper'},
h('div', {className:'box'},
h('span', {className:'title'}, '标题')
)
)
)
Copy the codeStudent: After translation yes!
Fang: Then your code and my code
const list = cp(1,
cp(2,
cp(3,
cp(4,
cp(5, null)
)
)
)
)
Copy the codeWhat’s the difference?
Student: Ok! I have long fallen in love with this stupid code, the fool is me…
React simply simplifies the nested code you use to build your UI into JSX and makes it look less cumbersome
Student: It seems I’m still confused by the way the code looks
So, that completes our second point: implementing a list with nested pairs. And I told you not to worry about the memory form, because the memory form of an abstract data structure can be continuous or discontinuous. This shows that functional thinking is more “advanced” and focuses on “abstract” things rather than “concrete” things like memory.
Student: Does “more abstract” mean “higher”?
Fang: Yes, but you should know that “advanced” is a “neutral word” in the programming world. High-level languages are equivalent to low-level languages, but the focus and form of expression are different.
Student: Anything else for today?
Fang: No, but there will be homework.
Student: Come on, I’ll try
The title is, add type to the following function (consider number only) and change it to single argument form
createPair = (a, b) => fn => fn(a, b)
first = pair => pair((x,y) => x)
second = pair => pair((x,y) => y)
Copy the codeStudent: Here we go:
type Fn = (x: number) => (y: number) => number
type Pair = (fn: Fn) => number
type CreatePair = (a:number) => (b:number) => Pair
const createPair: CreatePair = a => b => fn => fn(a)(b)
type First = (pair: Pair) => number
const first: First = pair => pair(x => y => x)
type Second = (pair: Pair) => number
const second: Second = pair => pair(x => y => y)
Copy the codeNot to mention, these three functions are easier to understand with the addition of types.
- CreatePair accepts two numbers and returns a Pair
- The Pair accepts a Fn and returns a number
- First accepts a Pair, passes Fn to the Pair, and returns a number
- Second is the same as First
However, I still have a hard time accepting that pair is a function. And I have to pass a function to pair to get a number, which is kind of confusing
Fang: Although you can write the code, you don’t understand the meaning
Student: Yes
Fang: Was the last time you felt this way when you were studying math
Student: Yeah, plug it into the formula anyway, and you get the answer
That’s right. That’s what a function feels like to a novice.
Student: So when will I really understand that a binary pair is a function
Fang: You can now simply assume that this function hides the data from you
Student: It’s kind of like that
Fang: We will discuss this later. Let’s call it a day
Student: Ok, bye!
Follow-up: juejin. Cn/post / 694203…
footnotes
- In fact, JS [1,2,3] is not stored continuously, but with objects to simulate, so it is stored randomly
- How does Haskell actually implement lists internally? We’re not going to talk about that right now