User Tools

Site Tools


cookbook:folding

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cookbook:folding [Monday, 25 June 2007 : 10:09:31]
127.0.0.1 external edit
cookbook:folding [Thursday, 12 February 2009 : 09:50:10] (current)
hvrooy
Line 1: Line 1:
 +====== Folding in lists (and sets) ======
 +
 +We have the list ''​xs = [ 1,3,2 ]''​.
 +We are interested in the sum of these list elements.
 +A solution for this problem is the following function:
 +<code chi>
 +func sum(val xs: [nat]) -> nat =
 +|[ var s: nat = 0
 +:: len(xs) > 0
 +   *> ( s:= s + hd(xs); xs:= tl(xs) )
 + ; ret s
 +]|
 +</​code>​
 +Initially the sum ''​s''​ equals zero.
 +As long as the list contains an element, we perform the addition
 +of the sum until so far and the head of the list.
 +We update the list by removing the head of the list, and we start the loop.
 +
 +We can use this function in the following process fragment:
 +<code chi>
 +|[ var xs: [nat] = [ 1,3,2 ], s: nat, ...
 +:: ...
 + ; s:= sum(xs)
 + // the result will be 6
 + ; ...
 +]|
 +</​code>​
 +
 +The above specification of function ''​sum''​ is a so called iterative
 +solution of the problem. Another way of specification is in a recursive way:
 +<code chi>
 +func sum(val xs: [nat]) -> nat =
 +|[ var s: nat = 0
 +:: ( len(xs) = 0 -> ret 0
 +   | len(xs) > 0 -> ret hd(xs) + sum(tl(xs))
 +   )
 +]|
 +</​code>​
 +Again the result will be 6.
 +A snapshot of the execution of the specification is:
 +<code chi>
 +  sum([1,​3,​2])
 += 1 + sum([3,2])
 += 1 + 3 + sum([2])
 += 1 + 3 + 2 + sum([])
 += 1 + 3 + 2 + 0
 += 6
 +</​code>​
 +
 +
 +===== Folding =====
 +
 +==== Adding ====
 + 
 +And still another way is by folding:
 +<code chi>
 +|[ var xs: [nat] = [1,3,2], s: nat, ...
 +:: ...
 + ; s:= ( +, x <- xs, x)
 + ; ...
 +]|
 +</​code>​
 +The pronunciation of this fragment is:
 +"add elements ''​x'',​ whereby ''​x''​ is drawn from list ''​xs''"​.
 +The elements 1,3,2 are drawn form the list ''​xs''​.
 +The elements are added by the plus (''​+''​) operator.
 +The final result will be 6.
 +
 +Another example of folding is the following.
 +We are interested in the sum of all odd elements of list ''​xs''​.
 +The specification is:
 +<code chi>
 +|[ var xs: [nat] = [1,3,2], s: nat, ...
 +:: ...
 + ; s:= ( +, x <- xs, x mod 2 > 0, x)
 + ; ...
 +]|
 +</​code>​
 +The result will be 4, as 1 and 3 are odd elements.
 +In this case we are using a filter ''​x mod 2 > 0''​
 +to consider only those elements that fulfill the condition.
 +
 +Another example delivers the sum of the square numbers of the list ''​xs''​.
 +We have:
 +<code chi>
 +|[ var xs: [nat] = [1,3,2], s: nat, ...
 +:: ...
 + ; s:= ( +, x <- xs, x * x)
 + ; ...
 +]|
 +</​code>​
 +
 +Another way of writing is by using a function ''​f''​.
 +This function maps the variable on the value:
 +<​code>​
 +func f(val x: nat) -> nat = |[ ret x * x ]|
 +</​code>​
 +We have for the last example the following fragment:
 +<code chi>
 +|[ var xs: [nat] = [1,3,2], s: nat, ...
 +:: ...
 + ; s:= ( +, x <- xs, f(x))
 + ; ...
 +]|
 +</​code>​
 +So far examples based on the operator ''​+''​.
 +
 +
 +
 +==== Multiplying ====
 +
 +It is also possible to use a multiply operator.
 +As an example we want to calculate the factorial (''​n!''​) of a number.
 +The factorial of a number is
 +''​fac(n) = n(n -1)(n - 2) ... 1''​.
 +So:
 +''​fac(3) = 3 . 2 . 1 = 6'',​ and
 +''​fac(5) = 5 . 4 . 3 . 2 . 1 = 120''​.
 +In a traditional manner we have the following function:
 +<code chi>
 +function fac(val n: nat) -> nat =
 +|[ var k: nat = n, p: nat = n
 +:: k > 1
 +   *> ( k:= k - 1; p:= p * k )
 + ; ret p
 +]|
 +</​code>​
 +
 +Or in an recursive manner:
 +<code chi>
 +function fac(val n: nat) -> nat =
 +|[ ( n > 1 -> ret n * fac(n - 1)
 +   | n = 1 -> ret 1
 +   )
 +]| </​code>​
 +
 +Or using folding:
 +<code chi>
 +function fac(val n: nat) -> nat =
 +|[ ret ( * , m <- 1 .. n, m) ]|
 +</​code>​
 +Note we use the construct ''​1..n''​ to generate the numbers 1,2, ..., n.
 +
 +==== Max and min ====
 +
 +It is also possible to use max operator ''​max''​ or
 +min operator ''​min''​. An example:
 +<code chi>
 +|[ var xs: [nat] = [1,3,2], s,t: nat, ...
 +:: ...
 + ; s:= ( max, x <- xs, x * x)
 + ; t:= ( min, x <- xs, x)
 + ; ...
 +]|
 +</​code>​
 +in this case the result of ''​s''​ will become 9,
 +and ''​t''​ will become 1.
 +
 +==== Concatenation ====
 + 
 +We have the concatenation operator. This operator adds
 +(glues) elements into one new list.
 +An example:
 +<code chi>
 +|[ var xs: [nat] = [1,3,2], ys: [nat], ...
 +:: ...
 + ; ys:= (  ++ , x <- xs, [ 2 * x ])
 + ; ...
 +]|
 +</​code>​
 +Every element of ''​xs''​ is multiplied by two, and glued into a new list
 +''​ys''​. In this case the value of ''​ys''​ will become ''​[2,​6,​4]''​.
 +
 +We assume that ''​xs''​ is a list with tuple elements of type
 +''​(nat,​nat)''​. The first elements is the identifier, the second
 +number is the number of parcel of an item.
 +And we are interested in the total number of parcel of the even item numbers.
 +We find:
 +<code chi>
 +|[ var xs: [(nat,nat)] = [(1,​10),​(2,​12),​(3,​16),​(6,​17)],​ s: nat, ...
 +:: ...
 + ; s:= ( + , x < xs, x.0 mod 2 = 0, x.1)
 + ; ...
 +]|
 +</​code>​
 +
 +===== Sets =====
 + 
 +Folding in sets
 +
 +As an example we have the set {1,3,2}.
 +The sum of these three set elements can be obtained by:
 +<code chi>
 +|[ var xr: {nat} = {1,3,2}, s: nat, ...
 +:: ...
 + ; s:= ( +, x <- xr, x )
 + ; ...
 +]|
 +</​code>​
 +
 +Folding in sets is similar to folding in lists.
 +In general we use suffix ''​r''​ to denote sets (and suffix ''​s''​ to denote lists), so we have ''​xr''​ and ''​xs''​.
 +
  
cookbook/folding.txt · Last modified: Thursday, 12 February 2009 : 09:50:10 by hvrooy