Notes to the Core Language of Mathematica II (List)

发表于 更新于 分类于

Lisp

As we have noted before, Mathematica is similar to Lisp. So let us talk about some characters of Lisp before we discuss the Mathematica.

Actually, Lisp is the abbreviation for list processing. List is an object take the form of:

1
(item1,item2,item3)

The list is also named as symbolic expression. The target of the interpreter of Lisp is to get the value of each symbol expression passed to it. The compiler takes item1 as the name of the function and item2 and item3 as variables. The method was invented by Jan Łukasiewicz from Poland, so it is named as Polish notation. Despite its difficulties for human to understand, it is convenient for the computer to cope with. When we compile a program, we need to convert the source code to abstract syntax tree. So the way we write Lisp is just writing a syntax tree.

In Mathematica, the function Treeform can get a expression's syntax tree.

1
TreeForm[(a + b^n)/z == x]

Have a try, and some surprises are waiting for you. If we want to write the expression above in Lisp, then it would take the form of

1
(==,(*,(+,a,(expt,b,n)),(expt,z,-1)),x)

Actually, the kernel of Mathematica understand the expression in the same way.

1
2
In:FullForm[(a + b^n)/z == x]
Out:Equal[Times[Plus[a,Power[b,n]],Power[z,-1]],x]

The the similarity is very conspicuous.

Everything is An Expression

==Everything is An Expression== is a philosophy that both Mathematica and Lisp follow (actually, it is more proper to say Mathematica get the idea from Lisp). Now let's review the definition of expression:

  1. An atom is an expression;
  2. If are expressions, is a expression.

Then we go on to illustrate why we say everything is an expression.

1
2
In: Map[FullForm,{a+b,a-b,a*b,a/b,a^b,a==b,a!=b,a<b,a<=b,a>b,a>=b,a&&b,a||b} ]
Out: {Plus[a,b],Plus[a,Times[-1,b]],Times[a,b],Times[a,Power[b,-1]],Power[a,b],Equal[a,b],Unequal[a,b],Less[a,b],LessEqual[a,b],Greater[a,b],GreaterEqual[a,b],And[a,b],Or[a,b]}

Though, expressions like a+b,a-b and a!=b is not take the form of , but Mathematica understands them in a different way. It's also noteworthy that the expression above could be write in a more convenient way, i.e. Map[f,expr] is equivalent to f\@ expr.

Computation is Rewriting

We could find that the first principle only care about the method we use to denote the object to be computed. It doesn't take the computation itself into consideration. ==Lisp is not good at computation==, and that's why Wolfram unsatisfied with Lisp. Mathematica got its way of computation from other functional programming languages like Haskell and OCaml.

In order to understand that, let's recall how we human perform computation. Just take a integrate as an example, Firstly, we rewrite as , then we computer and , and when we computer ，we rewrite it as . To conclude, when we perform computation, we always try to simplify the formulations until they could be computed directly. And Mathematica follow the same philosophy to compute, i.e. ==pattern matching== and ==rule substitution==. As a result, in Mathematica, to compute is to rewrite. (The computational model based on patterns and rules is called a rewriting system in mathematical logic or computer science.)

Function Matters

There is no rewriting system in Lisp, and Haskell and OCaml don't take everything as list, but we still classify them into one category which is so-called functional language. Why we do that?

In Lisp, we could add a ' to prevent a list get its' value, and the we take the list as some kind of data which is manipulative. When we combine some data to a List, we could use (eval L) to force the list get its value. Then the data L be converted to executable code again. We call Code-as-Data as the philosophy of Lisp.

In Haskell, we take every category as a set. Functions between categories are just the map between sets. It's easy to combine with by the operator .. What's more, all the map from to is also a set. Notice that all the maps from to is also a set which is called . The set is defined as a set automatically. As a result, all the bivariable functions from can be viewed as a one variable function from to . This operation is called currying. Both Code-as-Data and currying can be achieved in Mathematica and that's why people group it with languages like Lisp and Haskell.

The character is so important that we call it Mathematica's zeroth principle: Function Matters, not variables.

Expression and List

Brief Structure of An Expression or List

A expression is defined as an atom or a function like . Actually, we could also take atom as a special case of when there is no independent variables. So when we discuss expression in the future, it would take the form of .

Given a expression , is named a head.

1
2
In:Head /@ {1,1/2,True,"Number",a+b,a-b,a*b,a/b,(f+g)[x1,x2,x3]}
Out: {Integer, Rational, Symbol, String, Plus, Plus, Times, Times, f + g}

Note:f\@expr is Map[f,expr]

We could find that for atom, a symbol's head is always Symbol , a number's head depends on its type and could be Integer, Rational, Real, Complex, a string's head is always String, etc. We could decide whether a expression is an atom in this manner.

1
2
3
4
myAtomQ = 
   Function[ex, 
    MemberQ[{Symbol, Integer, Rational, Reals, Complex, String, Image},
      Head[ex]]];

However, sometimes we need to deal with the parameters of a expression. Then we take them out, but what we get turns out to be only a sequence compose of several expressions, and there is no head with them. But all of expressions of Mathematica must have a head. In order to deal with a expression without head, Mathematica introduce list and all of expressions don't have a head have a head of List. The case bellow shows that when we apply List to a expression, it become a list.

1
2
3
In: ex = f[x1, x2, x3];
    List @@ ex
Out:{x1,x2,x3}

List itself is also an inner function of Mathematica, and it could turn a sequence of expressions into as list. eg

1
2
In:List[1,2,3]
Out: {1,2,3}

@@, whose full name Apply, is also a functional operation and it change a expression's head. eg

1
2
3
4
In:Apply[g,h[x1,x2,x3]]
In:g@@h[x1,x2,x3]
Out:g[x1, x2, x3]
Out:g[x1, x2, x3]

There is also another type of list which is so-called Sequence. We could take sequence as a list without {} in both sides. Or we could say, list is turn a sequence into an object while sequence is something more basic.

1
2
3
4
5
6
In: ex = h[1, 2, 3]
	seq = Sequence @@ ex
	lst = List @@ ex
Out:h[1,2,3]
	Sequence[1,2,3]
	{1,2,3}

And when we want to convey the parameters of one expression to another expression, we can't get what we want because of the {}. Therefore we need to change the head of that expression to Sequence.

1
2
3
4
5
6
7
8
In: f[seq]
	f[lst]
	f @@ lst
	f[seq, lst, 4, 5, 6]
Out:f[1, 2, 3]
	f[{1, 2, 3}]
	f[1, 2, 3]
	f[1, 2, 3, {1, 2, 3}, 4, 5, 6]

Operations on Lists

Apart from Head and Apply , we could use the built-in function Part to visit expression inside compound expressions. It takes the form of Part[expr,number] or expr[[number]] and 0 is the head.

1
2
3
In: ex = f[x1, x2, x3];
	{ex[[0]], ex[[1]], ex[[2]], ex[[3]], ex[[4]]}
Out:{f, x1, x2, x3, f[x1, x2, x3][[4]]}

As we have discussed before, the type checking of Mathematica is not so strict and as a result of there is no ex[[4]], Mathematica return us a result of f[x1, x2, x3][[4]]. It's often the case that when Mathematica doesn't know what to do with our command, it would return what it get to us.

And for nested expressions, we can take Part more than one time.

1
2
3
In: ex = f[a, g[b, c], h[d, k[e, i], j]];
	ex[[3]][[2]][[2]]
Out:i

The operation could also write as ex[[3, 2, 2]]. There are many other ways to use Part, and we show this by four examples

1
2
3
4
5
6
7
8
In: ex[[-1, -2, -1]]
	ex[[{2, 3}]]
	ex[[1 ;; 2]]
	ex[[1 ;; 3 ;; 2]]
Out:i
	f[g[b, c], h[d, k[e, i], j]]
	f[a,g[b, c]]
	f[a, h[d, k[e, i], j]]

There are also some built-in functions for some Parts which are often used.

1
2
3
4
5
6
In: Function[op, op[f[x1, x2, x3, x4]]] /@ {First, Last, Rest, Most}
	Take[f[x1, x2, x3, x4], {2, 3}]
	Drop[f[x1, x2, x3, x4], {2, 3}]
Out:{x1, x4, f[x2, x3, x4], f[x1, x2, x3]}
    f[x2,x3]
    f[x1,x4]

For a given expression, there are two values matter. i.e. depth and length.

1
2
3
4
In: Length[f[g[x1, h[x2, x3]], x4]]
    Depth[f[g[x1, h[x2, x3]], x4]]
Out:2
    4

Construct a List

Like many other language, Range could be used to build a simple list.

1
Range[begin,end,step]

Only end is a must to this function. And Table, Array, Turples and Outer can be used to build a list too.

1
2
3
4
5
6
7
8
9
10
In: Table[i^2 + i + 1, {i, 10}]
    Table[KroneckerDelta[i, j - 1] + t KroneckerDelta[i, j + 4], {i, 5}, {j, 5}]//MatrixForm
Out:{3, 7, 13, 21, 31, 43, 57, 73, 91, 111}
    {{0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {t, 0, 0, 0, 0}}
In: Array[#^2 + # + 1 &, 10]
    #^2 + # + 1 & /@ Range[10]
Out:{3, 7, 13, 21, 31, 43, 57, 73, 91, 111}
    {3, 7, 13, 21, 31, 43, 57, 73, 91, 111}
In: Array[f, 5, 2, h]
Out:h[f[2],f[3],f[4],f[5],f[6]]

Tuples[List,n] means use members of the list to construct lists of n numbers and combine all possible answer to one list.

1
2
3
4
5
6
In: Tuples[Range[3], 3]
Out:{{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 1}, {1, 2, 2}, {1, 2, 3}, {1,
   3, 1}, {1, 3, 2}, {1, 3, 3}, {2, 1, 1}, {2, 1, 2}, {2, 1, 3}, {2, 
  2, 1}, {2, 2, 2}, {2, 2, 3}, {2, 3, 1}, {2, 3, 2}, {2, 3, 3}, {3, 1,
   1}, {3, 1, 2}, {3, 1, 3}, {3, 2, 1}, {3, 2, 2}, {3, 2, 3}, {3, 3, 
  1}, {3, 3, 2}, {3, 3, 3}}

Outer[f,list1,list2] group all the possible combinations of members of list1 and list2 and use them as the independent variables of f.

1
2
In: Outer[f, Range[3], Range[2]]
Out: {{f[1, 1], f[1, 2]}, {f[2, 1], f[2, 2]}, {f[3, 1], f[3, 2]}}

Search and Sort

MemberQ[expr,i] is used to judge whether i is a member of expr, while FreeQ[expr,i] is used to judge whether expr has a sub-expression which matches i. Both of them will return False, when i is the head of the expr.

1
2
3
4
5
In: ex = f[x1, x2, x3, x4];
    Function[i, MemberQ[ex, i]] /@ {f, x1, x2, x3, x4, x5, x6}
    Function[i, FreeQ[ex, i]] /@ {f, x1, x2, x3, x4, x5, x6}
Out:{False, True, True, True, True, False, False}
    {False, False, False, False, False, True, True}

And we could appoint the depth of searching for them.

Count[expr,i] is used to calculate how many times i appear in expr, appoint depth is also powered.

1
2
3
In: euler = (a + b^n)/n == x;
    {Count[euler, n], Count[euler, n, Infinity]}
Out:{0,2}

Use n means searching from 0th layer to nth layer, while use {n} means only search nth layer.

1
2
3
4
5
6
In: Position[euler, n]
    Function[level, Position[euler, n, level]] /@ {0, 1, 2, 3, 4}
    Function[level, Position[euler, n, level]] /@ {{3}, {4}}
Out:{{1, 1, 2, 2}, {1, 2, 1}}
    {{}, {}, {}, {{1, 2, 1}}, {{1, 1, 2, 2}, {1, 2, 1}}}
    {{{1, 2, 1}}, {{1, 1, 2, 2}}}

And we could use Select to choose members by self-defined rules.

1
2
In: Select[Prime /@ Range[10], OddQ]
    Select[Prime /@ Range[10], Mod[#, 4] == 1 &]