The first λ-calculus evaluating expression problem was very easy. The second one is similar:

Compute the value of (λx.x+1)((λy.y+2)3).

Just to make a bit more fun from it, let's solve it by writing the code in F#:

`(fun x -> x + 1)((fun`

]]>The first λ-calculus evaluating expression problem was very easy. The second one is similar:

Compute the value of (λx.x+1)((λy.y+2)3).

Just to make a bit more fun from it, let's solve it by writing the code in F#:

```
(fun x -> x + 1)((fun y -> y + 2)3)
|> printfn "%A"
```

And in JavaScript:

```
console.log((x => x + 1)((y => y + 2)(3)));
```

And in GO:

```
fmt.Println((func(x int) int { return x + 1; })((func(y int) int { return y + 2; })(3)))
```

Ok, In C#:

```
Console.WriteLine(((Func<int,int>)(x=>x+1))(((Func<int,int>)(y=>y+2))(3)));
```

More extreme, PHP:

```
print (function($x){ return $x+1; })((function($y){ return $y+2; })(3));
```

Let me know if you want some other language (perhaps I will not be able to do it assembly language) :-)

]]>The next set of problems are about performing calculations with λ-functions.

The first one is to check that the reader is confident with mixing λ-calculus and algebraic operators:

Compute the value of (λx.x + 1) 3

Let's use β-reduction on this expression:

```
(λx.x + 1) 3 ⇒ 3 + 1 ⇒ 4
```

Easy.

]]>The next set of problems are about performing calculations with λ-functions.

The first one is to check that the reader is confident with mixing λ-calculus and algebraic operators:

Compute the value of (λx.x + 1) 3

Let's use β-reduction on this expression:

```
(λx.x + 1) 3 ⇒ 3 + 1 ⇒ 4
```

Easy.

]]>The last one from reduction problems is following:

Reduce the following expression, using the beta-rule, to no more than one term. If the expression cannot be reduced, enter "CAN'T REDUCE".

(λg.((λf.((λx.(f(xx)))(λx.(f(xx)))))g))

Well, now I (and you, if you follow) understand

]]>The last one from reduction problems is following:

Reduce the following expression, using the beta-rule, to no more than one term. If the expression cannot be reduced, enter "CAN'T REDUCE".

(λg.((λf.((λx.(f(xx)))(λx.(f(xx)))))g))

Well, now I (and you, if you follow) understand the Lisp developers better. The number of parenthesis is quite close to critical in this expression.

The definition `(λg.((λf.(...)) g))`

just recalls the internal function with the same argument. It can be reduced to `λf.(...)`

.

Let's try to reduce `λf.(...)`

:

```
λf.(λx.(f (x x))) (λx.(f (x x))) =
λf.(f ((λx.(f (x x))) (λx.(f (x x))))) =
λf.(f (f ((λx.(f (x x))) (λx.(f (x x))))) =
λf.(f (... (f ((λx.(f (x x))) (λx.(f (x x)))))...))
```

It grows indefinitely and similar to the expression from the problem Reduction #3. So the answer is "CAN'T REDUCE".

Just out of curiosity let's see how it will look in F#:

```
let f4 g =
let f3 f =
let f1 x = f (x x)
let f2 x = f (x x)
f2 f1
f3 g
```

F# compiler cannot compile it with the errors:

```
Compilation error (line 3, col 21): Type mismatch.
Expecting a 'a but given a 'a -> 'b
The resulting type would be infinite when unifying ''a' and ''a -> 'b'
Compilation error (line 4, col 21): Type mismatch.
Expecting a 'a but given a 'a -> 'b
The resulting type would be infinite when unifying ''a' and ''a -> 'b'
```

]]>The third λ-calculus problem is a bit more advanced (although still simple):

Reduce the following expression, using the beta-rule, to no more than one term. If the expression cannot be reduced, enter "CAN'T REDUCE".

((λx.(x x)) (λx.(x x)))

"beta-reduction" is just recution by substituting

]]>The third λ-calculus problem is a bit more advanced (although still simple):

Reduce the following expression, using the beta-rule, to no more than one term. If the expression cannot be reduced, enter "CAN'T REDUCE".

((λx.(x x)) (λx.(x x)))

"beta-reduction" is just recution by substituting variable value in the function body with its value. Check Reductions #1 and Reductions #2 for more examples.

The expression `((λx.(x x)) (λx.(x x)))`

cannot be reduced. It is easy to see that applying reduction results with exactly the same expression. So the answer is "CAN'T REDUCE".

The second λ-calculus problem is following:

Reduce the following to no more than one term. If the expression cannot be reduced, enter "CAN'T REDUCE".

((λx.((λy.(x y)) x)) (λz.w))

Let's reduce the expressions:

- Framing parentheses are not required:
`(λx.((λy.(x y)) x)) (λz.w)`

- Rewrite

The second λ-calculus problem is following:

Reduce the following to no more than one term. If the expression cannot be reduced, enter "CAN'T REDUCE".

((λx.((λy.(x y)) x)) (λz.w))

Let's reduce the expressions:

- Framing parentheses are not required:
`(λx.((λy.(x y)) x)) (λz.w)`

- Rewrite function body with the argument being substituted with the value:
`((λy.((λz.w) y)) (λz.w))`

. - Remove parentheses again:
`(λy.((λz.w) y)) (λz.w)`

. - And substitute again:
`(λz.w) (λz.w)`

. - Performing application gives just "free" variable
`w`

.

So the expression `((λx.((λy.(x y)) x)) (λz.w))`

can be reduced to just `w`

.

The Lambda Calculus - Reductions #1 is rather unusual. Instead of submitting the code, the required submission is a shortening of the lambda-expression.

Reduce the following expression to no more than one term. ... ((λx.(x y))(λz.z))

There is a nice introduction to the lambda-calculus: A Tutorial Introduction to

]]>The Lambda Calculus - Reductions #1 is rather unusual. Instead of submitting the code, the required submission is a shortening of the lambda-expression.

Reduce the following expression to no more than one term. ... ((λx.(x y))(λz.z))

There is a nice introduction to the lambda-calculus: A Tutorial Introduction to the Lambda Calculus. Some relevant excerpts from it:

`<expression> := <name> | <function> | <application>`

`<function> := λ <name>.<expression>`

`<application> := <expression><expression>`

- An example of a function is the following: λx.x. This expression defines the identity function.
- Functions can be applied to expressions. An example of an application is

(λx.x)y. - In λ calculus all names are local to definitions. ... A name

not preceded by a λ is called a “free variable”.

In programming language terms, the λ is a keyword defining a function. It is followed by the list of arguments and then the function body, separated by dot. The "free" variable is just defined somewhere else and available in the current scope.

So the expression "((λx.(x y))(λz.z))" can be rewritten as following (I will give examples in JS and F# programming languages):

```
// JavaScript
((x) => (x(y)))((z) => z)
// F#
(fun x -> x y)(fun z -> z)
```

`(fun z -> z)`

is just an identity function. The entire expression is an application of the function that applies its argument to value with identity function as argument. So the expression returns `y`

and it is the right answer.

The next problem, Area Under Curves and Volume of Revolving a Curve, in mathematically advance so I introduce some therms and facts first.

*Numerical integration* is the measuring the area between function and axis, which is done by evaluating function in many points closing to each other and adding together

The next problem, Area Under Curves and Volume of Revolving a Curve, in mathematically advance so I introduce some therms and facts first.

*Numerical integration* is the measuring the area between function and axis, which is done by evaluating function in many points closing to each other and adding together all rectangles (or trapezoids) formed by points on axis and points on the functional curve. For many functions decreasing step between points decreases difference between calculated value and actual area.

*Continuous function* is a function that, roughly speaking, has graph without "holes" or "jumps", e.g. its graph is a single unbroken curve. The continuouty can be local, e.g. on some interval.

*Revolving a Curve* is a transformation of 2D curve into 3D shape by revolving the curve around the axis. The are many examples of such figures in turning machine YouTube videos.

*Volume of cylinder* can be computed by using the formula

$$V = π r^2 h$$

I'm going to rephrase the problem statement a bit:

Consider the algebraic expression given by:

$$a_1 x ^{b_1} + a_2 x ^{b_2} + ... + a_n x ^{b_n}$$

Evaluate a) the area bounded by the function between the given limits L and R and b) the volume of the solid figure obtained by revolving this curve around the x-axis. Use the step length 0.001. Limits can be from 1 to 20. b ∈ [-20, 20] ∩ ℕ.

The given function is continous on [1, 20] so it is ok to integrate it numerically.

The number of steps required to solve the problem is

$$ \frac{R - L} {step length} b n c < \frac{19} {0.001} 20 n c = 380000 n c$$

where n is the number of items in the expression (which is probably less than 50) and c is a some constant representing number of operations required to compute area and volume (probably about 5). So the rough estimation is 10^8 arithmetic operations in worst case. The cost of devision is something about 10^-8 so the worst case computation time should be around 1 second, which is good enough to just try to solve the problem without optimisations at all.

Let's split the problem into smaller chunks:

- Calculate x^y
- Calculate single item of the expression
- Calculate expression
- For every point calculate area and volume and return their sum

The expression can be defined as a list of two-items tuples:

```
let pi = System.Math.PI
let item a b x =
// x ** b is x^b (power operator)
a * (x ** b)
let expr cs x =
cs
|> List.fold (fun s c -> s + (item (fst c) (snd c) x)) 0.0
let numIntAndVol cs l r =
let folding s y =
let s, v, prev = s
(s + 0.001 * y, v + 0.001 * y * y * pi, y)
seq { l .. 0.001 .. r }
|> Seq.map (fun x -> expr cs x)
|> Seq.fold folding (0.0, 0.0, 0.0)
```

And now the main method:

```
[<EntryPoint>]
let main argv =
let a = Console.ReadLine().Split(' ') |> Array.toList |> List.map float
let b = Console.ReadLine().Split(' ') |> Array.toList |> List.map float
// this is a nice trick - it converts two lists to a list of tuples
let cs = List.zip a b
let limits = Console.ReadLine().Split(' ') |> Array.toList |> List.map float
let l, r = limits.[0], limits.[1]
let area, volume, _ = numIntAndVol cs l r
printfn "%A" area
printfn "%A" volume
0 // return an integer exit code
```

Input:

```
1 2 3 4 5
6 7 8 9 10
1 4
```

Output:

```
414.023
36024.18118
```

]]>This traffic light is based on the first example. The same resistor + LED is replicated three times and attached to the different pins.

The very common logic for traffic light is "STOP" for some time, then "CAUTION" for shorter time, and then "GO" for

]]>This traffic light is based on the first example. The same resistor + LED is replicated three times and attached to the different pins.

The very common logic for traffic light is "STOP" for some time, then "CAUTION" for shorter time, and then "GO" for same time as "STOP". There are some regional differences though, so please feel free to adapt it to your location an send me the code.

```
#define LED_RED 13
#define LED_YELLOW 12
#define LED_GREEN 11
#define TIME_GO 4000
#define TIME_CAUTION 1000
#define TIME_STOP 4000
void setup() {
pinMode(LED_RED, OUTPUT);
pinMode(LED_YELLOW, OUTPUT);
pinMode(LED_GREEN, OUTPUT);
}
void loop() {
// start with red / stop
digitalWrite(LED_RED, HIGH);
delay(TIME_STOP);
digitalWrite(LED_RED, LOW);
// yellow / caution
digitalWrite(LED_YELLOW, HIGH);
delay(TIME_CAUTION);
digitalWrite(LED_YELLOW, LOW);
// you can go / green
digitalWrite(LED_GREEN, HIGH);
delay(TIME_GO);
digitalWrite(LED_GREEN, LOW);
// and now back you yellow
digitalWrite(LED_YELLOW, HIGH);
delay(TIME_CAUTION);
digitalWrite(LED_YELLOW, LOW);
// and back to red on the next iteration
}
```

]]>The problem Evaluating e^x:

The series expansion of eˣ is given by

$$1 + x + \frac{x^2} {2!} + \frac{x^3} {3!} + \frac{x^4} {4!} + ...$$

Evaluate eˣ for given values of x by using the above expansion for the first 10 terms.

This problem is interesting because it

]]>The problem Evaluating e^x:

The series expansion of eˣ is given by

$$1 + x + \frac{x^2} {2!} + \frac{x^3} {3!} + \frac{x^4} {4!} + ...$$

Evaluate eˣ for given values of x by using the above expansion for the first 10 terms.

This problem is interesting because it can be solved in a number of ways, different in performance and limits.

First of all, let's try to solve the problem in straightforward way and sum n items of the power series (or more specifically Taylor series):

```
let power x y =
seq { 1..y } |> Seq.fold (fun m _ -> m * x) 1.0
let factorial x =
seq { 1..x } |> Seq.fold (fun m v -> m * float(v)) 1.0
let sum s =
s |> Seq.fold (fun s v -> s + v) 0.0
let ex x =
seq { 0..9 }
|> Seq.map (fun n -> (power x n) / (factorial n))
|> sum
printfn "%A" (ex 2.0)
```

`ex`

applies series function from 0 because `x^0/0! = 1`

and `x^1/1! = x`

.

Although this solution works good enough to pass the tests, it is easy to see that it does a lot of extra work on calcuating power and factorial, although most of the job is already done while calculating previous sequence item.

The improved solution is to pass the calculated power and factorial to the next step. It changes the program significally. The `power`

and `factorial`

functions are no longer requried as all calculations are done in `ex`

, which is now recursive and returns sum, power and factorial.

```
let rec ex x n =
match n with
| 0 -> (1.0, 1.0, 1.0)
| _ -> let s, p, f = ex x (n - 1)
let np = p * x
let nf = f * float(n)
(s + np / nf, np, nf)
let v, _, _ = ex 2.0 9
printfn "%A" v
```

]]>The problem Updating List requires learning how to generate one list from another.

Update the values of a list with their absolute values.

In many other programming languages the common approach is to update the array items: `a[i] = abs(a[i]);`

, e.g. modify the shared state. The functional

The problem Updating List requires learning how to generate one list from another.

Update the values of a list with their absolute values.

In many other programming languages the common approach is to update the array items: `a[i] = abs(a[i]);`

, e.g. modify the shared state. The functional way change the list implies using immutable data structures so instead of modifying the list let's generate the new one with negative elements inverted:

```
// this function returns new list created by inverting
// negative items in the given list arr
let f arr = arr |> List.map (fun v -> if v < 0 then -v else v)
//----------------DON'T MODIFY---------------
let input =
stdin.ReadToEnd().Split '\n'
|> Array.map(fun x -> int(x))
|> Array.toList
let print_out (data:int list) = List.iter (fun x -> printfn "%A" x) data
print_out (f(input))
```

]]>It is really exciting to do even small hardware project after so many years of software development. That's what I can say after making LED blinks with Arduino. That's the story how I made it.

A few months ago, while on vacation, I bought the localised Arduino starting kit with

]]>It is really exciting to do even small hardware project after so many years of software development. That's what I can say after making LED blinks with Arduino. That's the story how I made it.

A few months ago, while on vacation, I bought the localised Arduino starting kit with Arduino, breadboard (it is a board with array of holes) and many small electrical parts and wires. Arduino and breakboard being assembled together on a platform looks like this:

The guide recommends to download the Arduino IDE. Surprisingly, it is not necessary - it is possible to write code for the board just in browser with Arduino Web Editor. It compiles code in the cloud and then uploads the bytecode directly to the board right from the web page. Of course it is done through the plugin that is need to be installed in order to support this functionality.

When the editor starts, the board model should be selected in the list. When the board is connected, it should be possible to just verify and send the code to the board with single click on the button with arrow.

The simplest example is, probably, Blink. It only requires one 220 ohm resistor, LED and couple of connectors. It is simple, but playing with different LED timing is fun.

That is what is needed:

Make sure that it is 220 om resitor by checking its colors.

Now bend the resistor legs. It should look like this:

Connect the pin no. 13 with resistor, connect another resitor leg with longer LED's leg and finally connect shorter LED's leg with the ground.

Breadboard with all things connected:

After copying the example code to the editor and uploading it to the board it should start blinking. If it is not, then check the LED. It may be inserted incorrectly.

By combining the delays and power levels it is possible to send messages with Morse Code.

```
// https://en.wikipedia.org/wiki/Morse_code
void lA() { p(); s1(); ddd(); }
void lB() { ddd(); s1(); p(); s1(); p(); s1(); p(); }
void lC() { ddd(); s1(); p(); s1(); ddd(); s1(); p(); }
void lD() { ddd(); s1(); p(); s1(); p(); }
void lE() { p(); }
void lF() { p(); s1(); p(); s1(); ddd(); s1(); p(); }
void lG() { ddd(); s1(); ddd(); s1(); p(); }
void lH() { p(); s1(); p(); s1(); p(); s1(); p(); }
void lI() { p(); s1(); p(); }
void lJ() { p(); s1(); ddd(); s1(); ddd(); s1(); ddd();}
void lK() { ddd(); s1(); p(); s1(); ddd(); }
void lL() { p(); s1(); ddd(); s1(); p(); s1(); p(); }
void lM() { ddd(); s1(); ddd(); }
void lN() { ddd(); s1(); p(); }
void lO() { ddd(); s1(); ddd(); s1(); ddd(); }
void lP() { p(); s1(); ddd(); s1(); ddd(); s1(); p(); }
void lQ() { ddd(); s1(); ddd(); s1(); p(); s1(); ddd(); }
void lR() { p(); s1(); ddd(); s1(); p(); }
void lS() { p(); s1(); p(); s1(); p(); }
void lT() { ddd(); }
void lU() { p(); s1(); p(); s1(); ddd(); }
void lV() { p(); s1(); p(); s1(); p(); s1(); ddd(); }
void lW() { p(); s1(); ddd(); s1(); ddd(); }
void lX() { ddd(); s1(); p(); s1(); p(); s1(); ddd(); }
void lY() { ddd(); s1(); p(); s1(); ddd(); s1(); ddd(); }
void lZ() { ddd(); s1(); ddd(); s1(); p(); s1(); p(); }
void p() { digitalWrite(13, HIGH); u(); digitalWrite(13, LOW); }
void ddd() { digitalWrite(13, HIGH); u(); u(); u(); digitalWrite(13, LOW); }
void s1() { u(); }
void s3() { u(); u(); u(); }
void s7() { u(); u(); u(); u(); u(); u(); u(); }
void u() { delay(250); }
```

Now combine the message:

```
void _HELLO() { lH(); s3(); lE(); s3(); lL(); s3(); lL(); s3(); lO(); }
void _HUMANS() { lH(); s3(); lU(); s3(); lM(); s3(); lA(); s3(); lN(); s3(); lS(); }
```

And start sending it:

```
void loop() {
_HELLO(); s7(); _HUMANS();
}
```

]]>The problem List Length is interesting because it can be solved using mutable counter but it also can be solved in more functional way.

Count the number of elements in an array without using count, size or length operators (or their equivalents).

First, let's see on the solution using mutable

]]>The problem List Length is interesting because it can be solved using mutable counter but it also can be solved in more functional way.

Count the number of elements in an array without using count, size or length operators (or their equivalents).

First, let's see on the solution using mutable variable:

```
let len lst =
let mutable index = 0
for _ in lst do
index <- index + 1
index
```

The real challenge here is to implement it without using mutable state. The common way to do so is to use recursion and pattern matching:

```
let rec len lst =
match lst with
| [ ] -> 0
| [ _ ] -> 1
| _ :: tail -> 1 + len tail
```

While matching the lst first matched with empty list, then with list containing one argument, and then with list containing more than one argument. On the match it extracts tail (all elements except first) and applies `len`

to it.

The problem Sum of Odd Elements:

You are given a list. Return the sum of odd elements from the given list.

The solusion is basically just an invocation of the List.fold from the standard library:

```
let f arr =
arr
|> List.fold (fun s v -> if Math.
```

]]>The problem Sum of Odd Elements:

You are given a list. Return the sum of odd elements from the given list.

The solusion is basically just an invocation of the List.fold from the standard library:

```
let f arr =
arr
|> List.fold (fun s v -> if Math.Abs(v % 2) = 1 then s + v else s) 0
```

Math.Abs is required because for negative numbers % 2 returns either 0 or -1.

]]>The problem Reverse a List encourages to learn `List.rev`

.

You are given a list of elements. Reverse the list without using the reverse function.

The simplest implementation is not very efficient one but it works good enough to pass the tests:

```
let rev (lst : List<'T>) =
let
```

]]>The problem Reverse a List encourages to learn `List.rev`

.

You are given a list of elements. Reverse the list without using the reverse function.

The simplest implementation is not very efficient one but it works good enough to pass the tests:

```
let rev (lst : List<'T>) =
let length = List.length lst
seq { for i in (length-1) .. -1 .. 0 do yield lst.[i] }
|> Seq.toList
```

The main method:

```
[<EntryPoint>]
let main argv =
readItemsFromInput ()
|> Seq.toList
|> rev
|> Seq.iter (fun v -> printfn "%A" v)
0 // return an integer exit code
```

Complexity of the solution is O(N²) because getting list item is O(N) and it should be done for very item of the list. The alternative can be using structure with O(1). You can try to do it as an exercise.

]]>The problem Array Of N Elements requires to write the function that returns N items. The string serialisation of the data structure should be very specific and similar to `[ 1, 2, 3 ]`

.

In the previous solutions I've generated the items using sequences. If sequences was allowed, the solution would be

]]>The problem Array Of N Elements requires to write the function that returns N items. The string serialisation of the data structure should be very specific and similar to `[ 1, 2, 3 ]`

.

In the previous solutions I've generated the items using sequences. If sequences was allowed, the solution would be trivial: `let f n = seq { 1..n }`

. But the sequences are printed as `seq [1; 2; 3]`

so it is need to be converted to list either with `Seq.toList`

or `List.ofSeq`

.

The solution is:

```
let f n = seq { 1..n } |> List.ofSeq
```

]]>