|
id | a -> a | identity function |
|
(\$) | (a -> b) -> a -> b | application operator |
|
(.) | (b -> c) -> (a -> b) -> (a -> c) | function composition |
|
const | a -> b -> a | constant function |
|
curry | ((a, b) -> c) -> a -> b -> c | give function parameters separately instead of a pair |
|
uncurry | (a -> b -> c) -> ((a, b) -> c) | inverse of curry |
|
curry3 | ((a, b, c) -> d) -> a -> b -> c -> d | give function parameters separately instead of a tripl |
|
uncurry3 | (a -> b -> c -> d) -> ((a, b, c) -> d) | inverse of curry3 |
|
flip | (a -> b -> c) -> b -> a -> c | flips the order of the function parameters
|
Function `$` just applies given function and a parameter:
~~~
f $ x = f x
~~~
The precedence of the operator is very weak and it associates
to right. It can be used
to remove some parentheses in deeply nested expression. So
we can write
~~~
> text = "Lorem ipsum dolor sit amet, consectetur adipiscing elit."
> length
$ filter (\s -> length s > 4)
$ splitString text "[ ,.]"
5
~~~
instead of
~~~
> length (filter (\s -> length s > 4) (splitString text "[ ,.]"))
5
~~~
## Data structures
----
One of the simplest data structure is a pair:
~~~
> ("Citizen Kane", 1941)
("Citizen Kane", 1941)
~~~
As seen above, the different elements of the pair can have different types.
The components of the pair can be accessed with the functions `fst` and `snd`:
~~~
> fst ("Citizen Kane", 1941)
"Citizen Kane"
> snd ("Citizen Kane", 1941)
1941
~~~
Other tuple lenghts are also supported:
~~~
> ()
()
> ("1", 1, 1.0)
("1", 1, 1.0)
~~~
----
Pairs and other tuples are useful, when we want to return more than one value from a function:
~~~
> toPolarCoordinates (x,y) = (sqrt (x*x + y*y), atan2 y x)
> toRectangularCoordinates (r,angle) = (r*cos angle, r*sin angle)
> polar = toPolarCoordinates (3,-6)
> polar
(6.708203932499369, -1.1071487177940904)
> toRectangularCoordinates polar
(3.000000000000001, -6.0)
~~~
As seen in the above example, when tuples are given as parameters to the functions, they can
be pattern matched. In `toPolarCoordinates (x,y)` the components of the pair given
as a parameter to the function are bound to `x` and `y`.
A much less readable version of the above function would be:
~~~
> toPolarCoordinates p = (sqrt (fst p*fst p + snd p*snd p),
atan2 (snd p) (fst p))
~~~
Patterns can be nested. A nonsensical example:
~~~
> shuffle ((a,b), (c,d)) = ((c,b), (a,d))
> shuffle ((1,2), (3,4))
((3, 2), (1, 4))
~~~
----
### Remark
The following command produces an error ``Expected $\langle$Integer$\rangle$ got $\langle$String$\rangle$
~~~
> shuffle (("1","2"), ("3","4"))
~~~
althought the function definition doesn't seem to care about the contents of the values (even if they are all of different types).
This is a restriction of the current version of SCL Console: all functions you define are *monomorphic* meaning
that all types involved must be fully known. When this is not a case, the compiler chooses the types somewhat arbitrarily.
In SCL modules, there is no such restrictions and the compiler chooses the most generic type as possible for a function.
Therefore, if the `shuffle` were defined in a SCL module, the above command would work.
----
Maybe the most important datatype is a list that may
hold any number of values of the same type. Lists
are constructed by enclosing the values in brackets:
~~~
> [1, 2, 3, 4]
[1, 2, 3, 4]
~~~
Elements of the lists are accessed with `!` operator:
~~~
> l = [1, 2, 3]
> l!0
1
> l!2
3
~~~
The length of the list can be found out with `length`:
~~~
> length l
3
~~~
Two lists are joined together with `+` operator:
~~~
> [1, 2] + [3, 4]
[1, 2, 3, 4]
~~~
Finally, a list containing some range of integers can be constructed as
~~~
> [4..9]
[4, 5, 6, 7, 8, 9]
~~~
----
### Exercise
A quadratic equation $a x^2 + b x + c = 0$ has real solutions only if the discriminant
$\Delta = b^2 - 4ac$ is non-negative. If it is zero, the equation has one solution and
if it is positive, the equation has two solutions:
$${-b \pm \sqrt{\Delta} \over 2a}.$$
Write a function $`solveQuadratic`$ that solves a quadratic function whose
coefficients are given as parameters and returns a list containing all solutions
of the equation:
~~~
> solveQuadratic 1 1 (-2)
[1.0, -2.0]
> solveQuadratic 1 1 1
[]
~~~
----
Many useful tools for manipulating lists are higher order functions.
The function `map` applies a given function to all elements of a list
and produces a new list of the same length from the results:
$$`map`\ f\ [x_1,x_2,\ldots,x_n] = [f\ x_1,f\ x_2,\ldots,f\ x_n]$$
Here is couple of examples:
~~~
> map (\s -> "_" + s + "_") ["a", "b", "c"]
["_a_", "_b_", "_c_"]
> map ((*) 3) [1..4]
[3, 6, 9, 12]
~~~
Unwanted elements can be removed from a list by `filter` function:
~~~
> filter (\s -> length s > 4) ["small", "big", "large", "tiny"]
["small", "large"]
> isPrime p = filter (\d -> p `mod` d == 0) [2..p-1] == []
> filter isPrime [2..20]
[2, 3, 5, 7, 11, 13, 17, 19]
~~~
The function `foldl` computes an aggergate value over a list of values
by applying a binary function to the elements starting from the given initial element:
$${\tt foldl}\ (\oplus)\ x_0\ [x_1,x_2,\ldots,x_n] = (\cdots((x_0 \oplus x_1) \oplus x_2) \oplus \cdots \oplus x_n)$$
In practice:
~~~
> foldl (+) 0 [2,3,4]
9
> foldl (*) 1 [2,3,4]
24
> foldl max 0 [2,3,4]
4
~~~
The function `sum` is equivalent to `foldl (+) zero`, but is in
some cases implemented much more effeciently (for example for strings).
The function `concatMap` is similar to `map`, but it assumes
that the given function produces lists and concatenates the lists together:
~~~
> concatMap
(\(n,v) -> map (const v) [1..n])
[(3,"a"), (2,"l"), (1,"i")]
["a", "a", "a", "l", "l", "i"]
~~~
----
### Exercise
Define a generalized average function for lists:
$${\rm avgG}\ p\ [x_1,\ldots,x_{n}] = \left({x_1^p + \cdots + x_n^p \over n}\right)^{1 \over p}$$
----
### Exercise
One useful way for producing lists is to map a range expression. For example
~~~
> diffs (l :: [Integer]) = map (\i -> l!(i+1) - l!i) [0..length l-2]
> diffs [1,2,4,8,3]
[1, 2, 4, -5]
~~~
Use the pattern to reimplement the function `reverse` from the standard library
that reverses the order of elements in a list.
----
SCL supports *list comprehension* which allows to write
many list producing expressions with a syntax that closely
resembles the set comprehension from mathematics:
~~~
> l = [1..3]
> [2*x | x <- l]
[2, 4, 6]
> [(x,y) | x <- l, y <- l]
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
> [(x,y) | x <- l, y <- l, x < y]
[(1, 2), (1, 3), (2, 3)]
> [(x,y) | x <- l, y=4-x]
[(1, 3), (2, 2), (3, 1)]
~~~
As seen in the above examples, the left side of the vertical bar
can be any expression producing the elements of the list. The
right side of the bar is a list of producing statements:
`x <- l` considers all `x` in the list `l`,
`x = e` sets the value of `x` by the expression `e`
and any boolean expression like `x < y` filters the produced elements.
----
### Remark
SCL does not support yet pattern matching of lists althought it is supported in Haskell.
----
This is a list of some list functions provided by SCL standard library:
|
map | Functor a => (a -> b) -> f a -> f b | |
|
concatMap | (a -> [b]) -> [a] -> [b] | |
|
filter | (a -> Boolean) -> [a] -> [a] | |
|
filterJust | [Maybe a] -> [a] | |
|
foldl | (a -> b -> a) -> a -> [b] -> a | apply the given binary operation from left to right |
|
foldl1 | (a -> a -> a) -> [a] -> a | |
|
unfoldl | (b -> Maybe (a, b)) -> b -> [a] | |
|
unfoldr | (b -> Maybe (a, b)) -> b -> [a] | |
|
zip | [a] -> [b] -> [(a,b)] | combine elements in the two lists |
|
zipWith | (a -> b -> c) -> [a] -> [b] -> [c] | |
|
unzip | [(a,b)] -> ([a],[b]) | |
|
sort | Ord a => [a] -> [a] | sorts the elements in the list |
|
sortBy | Ord b => (a -> b) -> [a] -> [a] | sorts the elements by a given criteria |
|
sortWith | (a -> a -> Integer) -> [a] -> [a] | sorts the elements by a given comparison function |
|
(\\) | Eq a => [a] -> [a] -> [a] | removes from the first list the elements that occur in the second list |
|
range | Integer -> Integer -> [Integer] | |
|
reverse | [a] -> [a] | reverses the order of the elements in the list |
|
take | Integer -> [a] -> [a] | returns $n$ first elements of the list |
|
drop | Integer -> [a] -> [a] | removes $n$ first elements from the list and returns the tail |
|
lookup | Eq a => a -> [(a, b)] -> Maybe b | finds a pair from the list such that the first component
matches the given value and returns the second component |
|
and | [Boolean] -> Boolean | |
|
or | [Boolean] -> Boolean | |
|
any | (a -> Boolean) -> [a] -> Boolean | |
|
all | (a -> Boolean) -> [a] -> Boolean
|
----
One data structure used quite often is an optional value.
It is useful, if the function produces the result only for
some parameter values. Optional value is either
`Just value` or `Nothing`. Here is an example:
~~~
> safeSqrt x | x >= 0 = Just (sqrt x)
| otherwise = Nothing
> safeSqrt 2
Just 1.4142135623730951
> safeSqrt (-2)
Nothing
~~~
The type of the expressions `Just value` and `Nothing` is `Maybe t`,
where $`t`$ is the type of `value`.
Optional values can be handled with pattern matching
(the example is from the standard library):
~~~
> fromMaybe _ (Just value) = value
fromMaybe default Nothing = default
~~~
----
Sometimes it is useful to use pattern matching without
defining a new function for it. Therefore there is
`match` construct:
~~~
> match (1,2,3) with
(x,y,z) -> x+y+z
6
~~~
As with functions, there can be multiple cases and the
first matching case is chosen:
~~~
> match safeSqrt 3 with
Just v -> v
Nothing -> fail "Something bad happened."
~~~
## Types
----
Every expression in SCL has a type. Type determines the set of possible values
of the expression. They are used for detecting errors in SCL code, for choosing the
right implementation of a method (for example addition `(+)`) and for generating
efficient byte code.
When the type is monomorphic (does not contain type variables), it can be printed as
~~~
> typeOf "foo"
String
> typeOf [1,2,3]
[Integer]
~~~
----
Normally SCL compiler will infer the types of the expressions automatically and
you don't have to specify them manually. There are however situations where
explicit control of types is useful:
* You want to document the interface of your functions. It is good practice
to write a type annotation for all top-level functions declared in a SCL module.
Such declarations are not available in SCL Console:
~~~
fst :: (a,b) -> a
fst (x,y) = x
~~~
* SCL compiler cannot infer a type that satisfies all the required constraints:
~~~
> strId x = show (read x)
There is no instance for