exercises.org 53 KB
# -*- mode: org; fill-column: 80; -*-
#+TITLE: Exercises
#+AUTHOR: Zelphir Kaltstahl
#+STARTUP: content
#+STARTUP: indent
#+STARTUP: align
#+STARTUP: inlineimages
#+STARTUP: entitiesplain
#+STARTUP: nologdone
#+STARTUP: nologreschedule
#+STARTUP: nologredeadline
#+STARTUP: nologrefile
#+TODO: TODO WIP | DONE
#+DATE: [2021-11-09 Tue]
#+LANGUAGE: English
#+PRIORITIES: A C C
* About
:PROPERTIES:
:CUSTOM_ID: about
:END:
This org file contains solutions to the exercises of "Elements of ML Programming" by Jeffrey D. Ullman.
* Solutions
:PROPERTIES:
:CUSTOM_ID: solutions
:END:
** 2.1.1
#+name: 2-1-1-a
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
1 + 2 * 3
#+end_src
#+RESULTS: 2-1-1-a
:results:
val it = 7 : int
:end:
#+name: 2-1-1-b
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
5.0 - 4.2 / 1.4
#+end_src
#+RESULTS: 2-1-1-b
:results:
val it = 2.0 : real
:end:
#+name: 2-1-1-c
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
11 div 2 mod 3
#+end_src
#+RESULTS: 2-1-1-c
:results:
val it = 2 : int
:end:
-> ~div~ either has higher precedence than ~mod~ or is first evaluated, because it is on the left.
#+name: 2-1-1-d
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
"foo" ^ "bar" ^ ""
#+end_src
#+RESULTS: 2-1-1-d
:results:
val it = "foobar" : string
:end:
#+name: 2-1-1-e
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
3 > 4 orelse 5 < 6 andalso not (7<>8)
#+end_src
#+RESULTS: 2-1-1-e
:results:
val it = false : bool
:end:
#+name: 2-1-1-f
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
if 6 < 10 then
6.0
else
10.0
#+end_src
#+RESULTS: 2-1-1-f
:results:
val it = 6.0 : real
:end:
#+name: 2-1-1-g
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
0xAB+123
#+end_src
#+RESULTS: 2-1-1-g
:results:
val it = 294 : int
:end:
#+name: 2-1-1-h
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
0xAB < 123
#+end_src
#+RESULTS: 2-1-1-h
:results:
val it = false : bool
:end:
** 2.1.2
#+name: 2-1-2-a
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
8/4
#+end_src
- uses real division with integers
#+name: 2-1-2-b
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
if 2 < 3 then 4
#+end_src
- there is no ~if ... then ...~ expression in Standard ML
#+name: 2-1-2-c
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
1 < 2 and 5 > 3
#+end_src
- using ~and~ as boolean operator, which it is not
#+name: 2-1-2-d
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
6 + 7 DIV 2
#+end_src
- writing ~div~ in capital letters. SML is case sensitive.
#+name: 2-1-2-e
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
4. + 3.5
#+end_src
- ~4.~ is not a complete input. It is not a real number for SML.
#+name: 2-1-2-f
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
1.0 < 2.0 or 3 > 4
#+end_src
- using ~or~ as boolean operator, which it is not meant to be used for.
#+name: 2-1-2-g
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
#"a" ^ #"b"
#+end_src
- using concatenation for strings on characters
#+name: 2-1-2-h
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
123.
#+end_src
- ~123.~ is not a complete input
#+name: 2-1-2-i
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
1.0 = 2.0
#+end_src
- using ~=~ on reals, which is not allowed in SML
** 2.1.3
#+name: 2-1-3
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
print ("\"\\\\\\\" stands for the double-quote character, \\\n \
\\\which otherwise would be interpreted \\\n \
\\\as the string ender.\"\n")
#+end_src
#+RESULTS: 2-1-3
:results:
"\\\" stands for the double-quote character, \
\which otherwise would be interpreted \
\as the string ender."
val it = () : unit
:end:
** 2.1.4
#+name: 2-1-4-a
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
val cond1 = true;
val cond2 = false;
(* andalso implementation *)
if cond1 then
cond2
else
false;
(* orelse implementation *)
if cond1 then
true
else
cond2
#+end_src
** 2.2.1
#+name: 2-2-1
#+begin_src sml :results verbatim output replace drawer
(* a *)
floor 123.45;
(* b *)
floor ~123.45;
(* c *)
ceil 123.45;
(* d *)
ceil ~123.45;
(* e *)
ord #"Y";
(* f *)
chr 120;
(* g *)
real (ord #"N");
(* h *)
chr (trunc 97.0);
(* i *)
str #"Z";
#+end_src
#+RESULTS: 2-2-1
:results:
val it = 123 : int
:end:
** 2.2.2
1. ~ceil~ should be applied to reals, not to integers. If we already have an
integer, what is the point of applying ~ceil~?
2. The ~then~ and ~else~ branches return different types of values. A fix would
be to return ~7~, the integer, instead of ~7.0~ the real.
3. ~chr~ can only be used on ~255~ or lower.
4. ~chr~ can only be used on numbers > 0.
5. ~ord~ can only be used on characteres. We could write the /character/ ~#"3"~
instead.
6. ~chr~ can only be used on integers.
7. ~0~ is not a boolean value. Write an expression resulting in a boolean value
as a condition instead of ~0~.
8. ~ord~ can only be used on characters. ~"a"~ is a string. Write the character
~#"a"~ instead.
** 2.3.1
Choice of:
+ alphanumeric identifier (ordinary non-type values)
+ symbolic identifier
+ type representing identifier
+ not a valid identifier
Solution:
1. ~The7Dwarves~: alphanumeric indentifier
2. ~7Dwarves~: not a valid identifier, because it starts with a digit.
3. ~SevenDwarves,The~: not a valid identifier, because it contains a ~,~, which
cannot be part of any identifier.
4. ~'SnowWhite'~: type representing identifier
5. ~a<=b~: not a valid identifier, because it mixes symbolic identifier
characters with alphanumeric identifier characters.
7. ~hurrah!~: not a valid identifier, because it mixes symbolic identifier
characters with alphanumeric identifier characters.
8. ~#1~: not a valid identifier, mixing symbolic identifier characters with
alphanumeric identifier characters.
9. ~'123~: not a valid identifier. Apparently one cannot have a digit as a first
character after the single quote.
** 2.3.2
- ~a~, ~b~ and ~c~.
** 2.4.1
1. ~4~
2. ~3~
3. ~[4,5]~
4. ~[#"f",#"o",#"o"]~
5. ~"foo"~
6. ~["c","a","t"]~
7. ~["c","o","b","o","l"]~
8. ~"cat"~
** 2.4.2
1. accessing a position that does not exist
2. the empty list has no element in it, so there cannot be a head
3. using a list acccessor with a non-list argument
4. using ~explode~ with a non-string argument
5. using ~implode~ with non-char-list arguments
6. using ~::~ operator with two lists instead of an element and a list
7. the empty list has no tail
8. trying to use the append operator ~@~ with non-lists
9. using ~concat~ with a non-string-list
** 2.4.3
1. ~real * (string * int list)~
2. ~int list list~ (because ~nil~ is an alias for ~[]~)
3. ~(int * real) list~
4. ~char list * int list list~
** 2.4.4
1. No. Tuples have a non-variable length and as such the ML type system
distinguishes between 2-tuples and 3-tuples. Tuples can contain elements of
multiple types, which means that the type system needs to make sure to
provide suficient information by mentioning the type of each element, in
contrast to lists.
2. Yes. Lists are of variable length and the ML type system does not distinguish
between different lengths of lists. Lists can also contain only elements of
the same type, so having the information "int list" is sufficient for the
type system.
** 2.4.5
1. example:
#+begin_src sml
[[[1]]]
#+end_src
2. example:
#+begin_src sml
[(1, #"1")]
#+end_src
3. example:
#+begin_src sml
(["s"], (1, (2.0, "2.5")), 3)
#+end_src
4. example:
#+begin_src sml
(((1, 2), ([true]), 1.0), (2.0, "a"))
#+end_src
5. example:
#+begin_src sml
((true, 1), #"c")
#+end_src
6. example:
#+begin_src sml
(1.0, [[[[1]]]])
#+end_src
** 2.4.6
convert string of length 1 into its character
#+begin_src sml
hd(explode("a"));
#+end_src
** 3.1.1
1. code:
#+begin_src sml
fun cube (x: real) =
x * x * x;
#+end_src
2. code:
#+begin_src sml
fun min3 (a: int, b: int, c: int) =
let
fun min2 (a: int, b: int) =
if a <= b
then a
else b;
in
min2 (min2 (a, b), c)
end;
#+end_src
#+RESULTS:
: val min3 = fn : int * int * int -> int
3. code:
#+begin_src sml
fun third (lst: 'a list) =
hd(tl(tl(lst)));
#+end_src
#+RESULTS:
: val third = fn : 'a list -> 'a
4. code:
#+begin_src sml
fun reverse_3_tup (tup: 'a * 'b * 'c) =
(#3 tup, #2 tup, #1 tup);
#+end_src
#+RESULTS:
: val reverse_3_tup = fn : 'a * 'b * 'c -> 'c * 'b * 'a
5. code:
#+begin_src sml
fun third_char (str: string) =
hd (
tl (
tl (
explode str
)
)
);
#+end_src
#+RESULTS:
: val third_char = fn : string -> char
6. code:
#+begin_src sml
fun left_shift_list (lst: 'a list) =
tl lst @ [hd lst];
#+end_src
#+RESULTS:
: val left_shift_list = fn : 'a list -> 'a list
** 3.1.2
*** 1
#+begin_src sml
fun max (a: int, b: int) =
if a >= b then a else b;
fun min (a: int, b: int) =
if a <= b then a else b;
fun min_max_out_of_3 (a: int, b: int, c: int) =
[min(min(a, b), c), max(max(a, b), c)];
min_max_out_of_3 (2, 1, 3);
#+end_src
#+RESULTS:
: val max = fn : int * int -> int
*** 2
**** Quicksort
First consider quicksort implemented in Scheme (taken and improved readability
from [[https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Scheme]] (2021-07-04)):
#+begin_src scheme
(define split-by
(λ (lst pivot-test partitions-processor)
;; loop over elements, recursively partitioning into
;; elements, which satisfy the pivot-test and elements,
;; which do not satisfy the pivot-test.
(let loop ([low '()] [high '()] [lst lst])
(cond
[(null? lst)
;; TODO: Might be able to simply use the empty list
;; here, instead of applying the
;; partitions-processor.
(partitions-processor low high)]
[(pivot-test (car lst))
;; Collect element satisfying the pivot-test.
(loop low
(cons (car lst) high)
(cdr lst))]
[else
;; Collect element not satisfying the pivot-test.
(loop (cons (car lst) low)
high
(cdr lst))]))))
(define quicksort
(λ (lst greater-than?)
(cond
[(null? lst) '()]
[else
(split-by
;; Use only the rest of the list, as the first
;; element is used as pivot element.
(cdr lst)
;; Predicate for determining whether an element is
;; greater than the pivot element. Here naive
;; approach of using the first element as a pivot
;; element.
(λ (x) (greater-than? x (car lst)))
;; Lambda processing partitions. What to do with the
;; 2 partitions after partitioning using the
;; greater-than? predicate as pivot-test.
(λ (low high)
;; Careful: append has O(n) runtime.
(append
;; recursive call for lesser elements
(quicksort low greater-than?)
;; pivot element
(list (car lst))
;; recursive call for greater elements
(quicksort high greater-than?))))])))
(define (quicksort-2 lst gt?)
(if (null? lst)
'()
(append (quicksort (filter (lambda (x) (gt? (car lst) x)) (cdr lst))
gt?)
;; needs to be a list for append to work
(list (car lst))
(quicksort (filter (lambda (x) (not (gt? (car lst) x))) (cdr lst))
gt?))))
#+end_src
We can rewrite this in SMLNJ:
#+name: quicksort
#+begin_src sml
fun quicksort (nil,
greater_than: 'a * 'a -> bool,
partition_pivot_not_pivot: 'a list -> 'a * 'a list) = nil
| quicksort (lst: 'a list,
greater_than: 'a * 'a -> bool,
partition_pivot_not_pivot: 'a list -> 'a * 'a list) =
let
val (pivot_elem, not_pivot_elems) = partition_pivot_not_pivot lst;
in
let
val (low, high) = List.partition (fn x => greater_than(x, pivot_elem)) not_pivot_elems;
in
quicksort(low, greater_than, partition_pivot_not_pivot)
@
[pivot_elem]
@
quicksort(high, greater_than, partition_pivot_not_pivot)
end
end;
#+end_src
**** Solution
And then we can use it as follows:
#+begin_src sml
<>
fun sorted_triple (a: int, b: int, c: int) =
quicksort ([a,b,c],
(fn (a, b) => a > b),
(fn lst => (hd lst, tl lst)));
#+end_src
*** 3
#+begin_src sml
fun round_tenth (num: real) =
Real.fromInt(round(num * 10.0)) / 10.0;
#+end_src
*** 4
#+begin_src sml
fun delete_second (lst: 'a list) =
if length(lst) >= 2
then
let
val (a::b::rest) = lst;
in
a :: rest
end
else
lst;
#+end_src
** 3.1.3
*** 1
8
*** 2
11
*** 3
8
*** 4
10
*** 5
18
*** 6
17
** 3.2.1
*** 1
#+begin_src sml
fun fac 0 = 1
| fac 1 = 1
| fac n =
let
fun iter 1 prod = prod
| iter remaining_factors prod =
iter (remaining_factors - 1) (prod * remaining_factors);
in
if n > 0
then iter n 1
else raise Fail "n must be 0 or greater"
end;
#+end_src
*** 2
#+begin_src sml :results output verbatim drawer replace
fun cycle (lst: 'a list, i: int) =
let
fun left_shift_list (lst: 'a list) =
tl lst @ [hd lst];
in
if i > 0
then
cycle (left_shift_list(lst), (i - 1))
else
lst
end;
cycle ([1,2,3,4,5], 3);
#+end_src
#+RESULTS:
:results:
val cycle = fn : 'a list * int -> 'a list
:end:
*** 3
#+begin_src sml :results output verbatim drawer replace
fun duplicate_elements_of_list (lst: 'a list) =
if null(lst)
then []
else
let
val first = hd lst;
in
first :: first :: duplicate_elements_of_list (tl lst)
end;
duplicate_elements_of_list [1,2,3,4];
#+end_src
#+RESULTS:
:results:
val duplicate_elements_of_list = fn : 'a list -> 'a list
:end:
*** 4
#+begin_src sml :results output verbatim drawer replace
fun len (lst: 'a list) =
if null lst
then
0
else
1 + len(tl(lst));
#+end_src
*** 5
#+begin_src sml :results output verbatim drawer replace
fun pow (base: real, exponent: int) =
let
fun iter (base: real, exponent: int, product: real) =
if exponent = 1
then product * base
else iter (base, (exponent - 1), (product * base));
in
if exponent = 0
then 1.0
else iter (base, exponent, 1.0)
end;
pow (8.5, 3);
#+end_src
*** 6
#+begin_src sml :results output verbatim drawer replace
fun find_largest (lst: real list) =
foldl (fn (elem, prev) => if elem > prev
then elem
else prev)
Real.negInf
lst;
find_largest [
2.0,
7456.0,
3.0,
878.0,
2346.0,
8768.0,
2.0,
2.0,
42.0,
767.0,
8768.0,
35.0,
32.0,
423.0,
92346.0
];
#+end_src
#+RESULTS:
:results:
val find_largest = fn : real list -> real
:end:
** 3.2.2
*** 1
#+begin_src sml :results output verbatim drawer replace
fun foo (a,b,c,d) =
if a = b
then c + 1
else
if a > b
then c
else
b + d;
#+end_src
1. The return types of all branches must agree. So if one branch returns an integer, all branches must return an integer.
2. For overloaded operators like ~+~, the operands need to have the same type. If one operand is an integer, then so must the other be.
3. The branch ~then c + 1~ returns an integer, because ~1~ is an integer and thus ~c~ must be an integer and the operator ~+~ for integers returns and ~int~.
4. Subsequently all other branches must return ~int~.
5. The branch ~else b + d~ must return an ~int~ as well. ~b + d~ will only return an ~int~, if ~b~ and ~d~ are both ~int~.
6. The ~=~ operator can only compare numbers of same type and not of type ~real~.
7. Since we already know the type of ~b~ to be ~int~, ~a~ must also be an ~int~.
** 3.2.3
#+begin_src sml :results output verbatim drawer replace
fun f (a: int, b, c, d, e) = ...
#+end_src
*** 1
#+begin_src sml :results output verbatim drawer replace
if a < b + c then d else e
#+end_src
- a: int
- b: int
- c: int
- d and e of same type
- f returns value of same type as d and e
*** 2
#+begin_src sml :results output verbatim drawer replace
if a < b then c else d
#+end_src
- a: int
- b: int
- c and d have same type
- e is unused and of unknown type
- f returns value of same type as c and d
*** 3
#+begin_src sml :results output verbatim drawer replace
if a < b then b + c else d + e
#+end_src
- a: int
- b: int
- c: int
- d: int
- e: int
- f returns int
*** 4
#+begin_src sml :results output verbatim drawer replace
if a < b then b < c else d
#+end_src
- a: int
- b: int
- c: int
- d: bool
- e is unused and of unknown type
- f returns bool
*** 5
#+begin_src sml :results output verbatim drawer replace
if b < c then a else c + d
#+end_src
- a: int
- b: int
- c: int
- d: int
- e is unused and of unknown type
- f returns int
*** 6
#+begin_src sml :results output verbatim drawer replace
if b < c then d else e
#+end_src
- a: int
- b: int
- c: int
- d and e of same type
- f returns value of same type as d and e have
*** 7
#+begin_src sml :results output verbatim drawer replace
if b < c then d + e else d * e
#+end_src
- a: int
- b and c of same type (implementation assumes ~int~, as long as ~real~ is not specified explicitly as type of the arguments of the function.
- d and e of same type
- f returns value of same type as d and e have
** 3.2.4
*** 1
#+begin_src sml :results output verbatim drawer replace
fun fac 0 = 1
| fac 1 = 1
| fac n =
let
fun iter 1 prod = prod
| iter remaining_factors prod =
iter (remaining_factors - 1) (prod * remaining_factors);
in
if n > 0
then iter n 1
else raise Fail "n must be 0 or greater"
end;
#+end_src
At each iteration ~remaining_factors~ is reduced by ~1~ and ~prod~ multiplied by ~remaining_factors~. The environment does not really change anything else than that, because the stack frame is reused due to tail call opimization. When all is done, ~prod~ is returned and the stack frame cleaned up.
*** reverse
**** reverse using pattern matching (recommended)
#+begin_src sml
fun reverse nil = nil
| reverse (x::xs) =
reverse (xs) @ [x];
#+end_src
**** reverse using null predicate
#+begin_src sml
fun reverse2 (lst: 'a list) =
if null(lst)
then nil
else
reverse2 (tl(lst)) @ [hd(lst)];
#+end_src
**** alternative
#+begin_src sml
fun reverse3 nil = nil
| reverse3 (lst: 'a list) =
let
fun reverse_helper (lst, acc) =
if null(lst)
then acc
else reverse_helper (tl (lst), hd (lst) :: acc);
in
reverse_helper(lst, nil)
end;
#+end_src
**** reverse using foldl
This is actually doing the same as ~reverse3~ above, but perhaps more elegant.
#+begin_src sml
fun reverse4 nil = nil
| reverse4 (lst: 'a list) =
(* cannot call foldl with tuple notation, have to call it with curried notation *)
foldl op:: nil lst;
#+end_src
*** make a long list
#+begin_src sml
fun range (i: int) =
if i = 0
then nil
else i :: range (i - 1);
#+end_src
*** merge two sorted lists into a sorted list
#+begin_src sml
fun merge (nil, nil) = nil
| merge (lst1, nil) = lst1
| merge (nil, lst2) = lst2
| merge (lst1 as x::xs, lst2 as y::ys) =
if y < x
then y :: merge(lst1, ys)
else x :: merge(xs, lst2);
#+end_src
** 3.3.1
*** a
This solution already uses 3 patterns, which are simple numbers or arbitrary things.
#+begin_src sml
fun fac 0 = 1
| fac 1 = 1
| fac n =
let
fun iter 1 prod = prod
| iter remaining_factors prod =
iter (remaining_factors - 1) (prod * remaining_factors);
in
if n > 0
then iter n 1
else raise Fail "n must be 0 or greater"
end;
#+end_src
*** b
#+name: printer
#+begin_src sml :noweb yes :results output verbatim drawer replace
datatype primitives_wrapper =
Int of int | Real of real | String of string
datatype compound_wrapper =
IntList of int list |
RealList of real list |
StringList of string list;
fun int_list_to_string lst =
String.concatWith ", " (map (fn num => Int.toString(num)) lst);
fun real_list_to_string lst =
String.concatWith ", " (map (fn num => Real.toString(num)) lst);
fun string_list_to_string lst =
String.concatWith ", " ((map (fn str => "\"" ^ str ^ "\"") lst));
fun myprint (lst: compound_wrapper) =
case lst of
IntList lst => print("[" ^ (int_list_to_string lst) ^ "]" ^ "\n")
| RealList lst => print("[" ^ (real_list_to_string lst) ^ "]" ^ "\n")
| StringList lst => print("[" ^ (string_list_to_string lst) ^ "]" ^ "\n");
#+end_src
#+begin_src sml :noweb yes :results output verbatim drawer replace
fun left_shift_list nil = nil
| left_shift_list (x::xs) =
xs @ [x];
#+end_src
#+RESULTS:
:results:
val left_shift_list = fn : 'a list -> 'a list
:end:
*** c
#+begin_src sml :results output verbatim drawer replace
fun left_shift_list nil = nil
| left_shift_list (x::xs) =
xs @ [x];
fun cycle (nil, i: int) = nil
| cycle (x::nil, i: int) = [x]
| cycle (xs, 0) = xs
| cycle (xs, i: int) =
if i > 0
then
cycle (left_shift_list(xs), (i - 1))
else
xs;
#+end_src
#+RESULTS:
:results:
val cycle = fn : 'a list * int -> 'a list
:end:
*** d
#+begin_src sml :results output verbatim drawer replace
fun duplicate_elements nil = nil
| duplicate_elements (x::xs) =
x :: x :: duplicate_elements(xs);
#+end_src
#+RESULTS:
:results:
val cycle = fn : 'a list * int -> 'a list
:end:
*** e
The optimal solution would be something like the following:
#+begin_src sml :results output verbatim drawer replace
fun expt (0.0, i: int) = 0.0
| expt (1.0, i: int) = 1.0
| expt (x: real, 0) = 1.0
| expt (x: real, 1) = x
| expt (x: real, i: int) =
let
fun iter (base: real, exponent: int, product: real) =
if exponent = 1
then
product * base
else
iter (base, (exponent - 1), (product * base));
in
iter (x, i, 1.0)
end;
#+end_src
However, pattern matching on reals like that does not work, because reals are not an equal type, a type, which can be compared using equal. So one has to take the x as is and leave those cases away:
#+begin_src sml :results output verbatim drawer replace
fun expt (x, 0) = 1.0
| expt (x, 1) = x
| expt (x, i) =
let
fun iter (base: real, exponent: int, product: real) =
if exponent = 1
then
product * base
else
iter (base, (exponent - 1), (product * base));
in
iter (x, i, 1.0)
end;
#+end_src
#+RESULTS:
:results:
val expt = fn : real * int -> real
:end:
*** f
#+begin_src sml :results output verbatim drawer replace
fun find_max xs =
let
fun iter (nil, x) = x
| iter (x::xs, prev_max) =
if x > prev_max
then
iter (xs, x)
else
iter (xs, prev_max);
in
iter (xs, Real.negInf)
end;
#+end_src
** 3.3.2
#+begin_src sml :results output verbatim drawer replace
fun flip_pairs (x1::x2::xs) = x2 :: x1 :: flip_pairs(xs)
| flip_pairs (x::nil) = x :: nil
| flip_pairs nil = nil;
#+end_src
** 3.3.3
#+begin_src sml :results output verbatim drawer replace
fun remove_nth_member (nil, n) = nil
| remove_nth_member (x::xs, 0) = xs
| remove_nth_member (x::xs, n) =
if n = 0
then
xs
else
x :: remove_nth_member (xs, (n - 1));
#+end_src
#+RESULTS:
:results:
val remove_nth_member = fn : 'a list * int -> 'a list
:end:
** 3.3.4
#+begin_src sml :results output verbatim drawer replace
(1) fun sumLists(nil) = 0
(2) | sumLists(nil::YS) = sumLists(YS)
(3) | sumLists((x::xs)::YS) = x + sumLists(xs::YS);
sumLists([[1, 2], nil, [3]])
-> case 3: x = 1, xs = [2], YS = [nil, [3]]
-> 1 + sumLists([[2], nil, [3]])
-> case 3: x = 2, xs = nil, YS = [nil, [3]]
-> 1 + 2 + sumLists([nil, nil, [3]])
-> case 2: YS = [nil, [3]]
-> 1 + 2 + sumLists([nil, [3]])
-> case 2: YS = [[3]]
-> 1 + 2 + sumLists([[3]])
-> case 3: x = 3, xs = nil, YS = nil
-> 1 + 2 + 3 + sumLists(nil)
-> case 1:
-> 1 + 2 + 3 + 0
-> 6
#+end_src
** 3.3.5
*** a
#+begin_src sml :results output verbatim drawer replace
(* pattern was given as: (x::y::zs, w) *)
(["a", "b", "c"], ["d", "e"])
(*
->
x = "a",
y = "b",
zs = ["c"],
w = ["d", "e"]
,*)
#+end_src
*** b
#+begin_src sml :results output verbatim drawer replace
(* pattern was given as: (x::y::zs, w) *)
(["a", "b"], 4.5)
(*
->
x = "a",
y = "b",
zs = nil,
w = 4.5
,*)
#+end_src
*** c
#+begin_src sml :results output verbatim drawer replace
(* pattern was given as: (x::y::zs, w) *)
([5], [6, 7])
(* -> does not match *)
#+end_src
* 3.3.6
#+begin_src sml
[(x,y),zs]
[,] __ zs
|
|__ (,) __ y
|
|__ x
[,] __ nil
|
|__ (,) __ 3
|
|__ (1,2)
#+end_src
* 3.3.7
#+begin_src sml
open IntInf;
fun square 0 = 0
| square n =
(square (n - 1)) + (2 * n) - 1;
#+end_src
* 3.3.8
#+begin_src sml
fun sort_pairs nil = nil
| sort_pairs ((pair as (elem1, elem2)) :: nil) =
if elem1 > elem2
then (elem2, elem1) :: nil
else pair :: nil
| sort_pairs ((pair as (elem1, elem2)) :: pairs) =
if elem1 > elem2
then (elem2, elem1) :: sort_pairs pairs
else pair :: sort_pairs pairs;
#+end_src
* 3.3.9
#+name: vowel_functions
#+begin_src sml :noweb yes
fun is_vowel c =
let
val vowels = [
#"a", #"e", #"i", #"o", #"u", #"A", #"E", #"I", #"O", #"U"
];
in
case List.find (fn elem => elem = c) vowels
of
SOME c => true
| NONE => false
end;
fun starts_with_vowel nil = false
| starts_with_vowel (chars: char list as (c::_)) =
is_vowel c;
#+end_src
* 3.3.10
#+name: list_procs
#+begin_src sml
fun take_until pred nil = []
| take_until pred (x::xs) =
if pred x
then []
else x :: (take_until pred xs);
fun drop_until pred nil = []
| drop_until pred (lst as (x::xs)) =
if pred x
then
lst
else
drop_until pred xs;
#+end_src
#+name: string_procs
#+begin_src sml
<>
fun string_take_until char_pred str =
let
val chars = String.explode str;
in
String.implode (take_until char_pred chars)
end;
fun string_drop_until char_pred str =
let
val chars = String.explode str;
in
String.implode (drop_until char_pred chars)
end;
#+end_src
#+begin_src sml
<>
<>
fun pig_latin "" = ""
| pig_latin word =
if starts_with_vowel (String.explode word)
then
word ^ "yay"
else
let
val non_vowel_prefix = string_take_until is_vowel word;
val vowel_and_rest_suffix = string_drop_until is_vowel word;
in
vowel_and_rest_suffix ^
non_vowel_prefix ^
"ay"
end;
#+end_src
* 3.3.11 - representation of sets as single linked lists
#+name: set_procs
#+begin_src sml :noweb yes
fun member (item, nil) = false
| member (item, x::xs) =
item = x orelse member (item, xs);
fun delete (item, nil) = []
| delete (item, x::xs) =
if item = x
then xs
else x :: delete (item, xs);
fun insert (item, nil) = [item]
| insert (item, lst as x::xs) =
if item = x
then lst
else x :: insert (item, xs);
#+end_src
* 3.3.12 - prepend to all sublists
#+begin_src sml
fun prepend_to_all (elem, nil) = []
| prepend_to_all (elem, l::ls) =
(elem :: l) :: (prepend_to_all (elem, ls));
#+end_src
* 3.3.13 - powerset
#+begin_src sml :noweb yes
fun prepend_to_all (elem, nil) = []
| prepend_to_all (elem, l::ls) =
(elem :: l) :: (prepend_to_all (elem, ls));
(* my first working solution *)
fun powerset lst =
let
fun iter (acc, nil) = acc
| iter (acc, remaining as x::xs) =
iter (acc @ (prepend_to_all (x, acc)), xs);
in
iter ([[]], lst)
end;
(* shorter version which the book meant to hint at *)
fun powerset (x::xs) =
prepend_to_all (x, (powerset xs)) @ (powerset xs)
| powerset nil = [[]];
#+end_src
* 3.3.14 - products of differences
#+begin_src sml
fun product_of_differences (a, nil) = a
| product_of_differences (a, lst) =
(* using foldl to do 2 things in one pass over the list *)
foldl (fn (b, accumulated) => accumulated * (a - b))
1.0
lst;
(* not sure what to name this function *)
fun unnamed_func nil = 1.0
| unnamed_func (x::nil) = 1.0
| unnamed_func (x::xs) =
product_of_differences (x, xs);
#+end_src
* 3.3.15 - is empty list?
#+begin_src sml
fun is_empty nil = true
| is_empty _ = false;
#+end_src
#+RESULTS:
: val is_empty = fn : 'a list -> bool
* 3.3.16 - deduction of inference
The given function:
#+begin_src sml
fun sumPairs nil = 0
| sumPairs ((x,y)::zs) = x + y + (sumPairs zs);
#+end_src
+ ML infers the result type from the first pattern, where the result is the integer 0. All pattern matching branches must have the same result type, so the return type of the function must be ~int~.
+ Only integers add up to integers. Reals do only add up to reals and other types do not add up to ~int~ either.
+ To fulfill the condition, that all pattern matching branches must have the same result type, the addition of ~x + y + (sumPairs zs)~ must consist of integers.
+ This means, that ~x~ and ~y~ must be of type ~int~.
+ ~x~ and ~y~ are captured in the pattern ~((x,y)::zs)~.
+ This means, that at least at the beginning of the list, there must be a tuple of ~(x,y)~, which are of type ~int~.
+ The function assumes, that this remains true for all subsequent recursive calls.
+ In ML it is not possible to create a list, which consists of elements of inequal types.
+ If the first element of the list is a 2-tuple of elements of type ~int~, then so must the rest of the list be.
* 3.3.x - split and merge
#+name: split
#+begin_src sml :noweb yes
fun split nil = (nil, nil)
| split [a] = ([a], nil)
| split (a::b::cs) =
let
val (M, N) = split cs;
in
(a::M, b::N)
end;
#+end_src
#+RESULTS:
: val split = fn : 'a list -> 'a list * 'a list
#+name: merge
#+begin_src sml :noweb yes
(* merge 2 already sorted lists *)
fun merge less (nil, M) = M
| merge less (N, nil) = N
| merge less (L1 as x::xs, L2 as y::ys) =
if less (x, y)
then x :: merge less (xs, L2)
else y :: merge less (L1, ys);
#+end_src
#+RESULTS: merge
: val merge = fn : int list * int list -> int list
#+name: merge_sort
#+begin_src sml :noweb yes
<>
<>
fun merge_sort less nil = nil
| merge_sort less [a] = [a]
| merge_sort less lst =
let
(* split list in partitions of elements of alternating indices *)
val (part1, part2) = split lst;
(* sort parts in recursive calls *)
val sorted_part1 = merge_sort less part1;
val sorted_part2 = merge_sort less part2;
in
merge less (sorted_part1, sorted_part2)
end;
#+end_src
#+RESULTS: merge_sort
: val split = fn : 'a list -> 'a list * 'a list
* 3.4.1 - exponentiation function
#+begin_src sml
open IntInf;
fun expt_by_1000 0 = 0
| expt_by_1000 1 = 1
| expt_by_1000 x =
let
fun iter (accumulated, exponent) =
if exponent < 2
then accumulated * x
else iter (accumulated * x, exponent - 1);
in
iter (1, 1000)
end;
#+end_src
* 3.4.2
#+begin_src sml
fun split nil = (nil, nil)
| split [a] = ([a], nil)
| split (a::b::cs) =
let
val left_and_right = split cs;
in
(a::(#1 left_and_right), b::(#2 left_and_right))
end;
#+end_src
#+RESULTS:
: val split = fn : 'a list -> 'a list * 'a list
* 3.4.3 - powerset improved
#+begin_src sml
fun prepend_to_all (elem, nil) = []
| prepend_to_all (elem, l::ls) =
(elem :: l) :: (prepend_to_all (elem, ls));
(* shorter version which the book meant to hint at *)
fun powerset nil = [[]]
| powerset (x::xs) =
let
val ps = powerset xs;
in
prepend_to_all (x, ps) @ ps
end;
#+end_src
* 3.4.4 - maximum improved
There is no useful place to put a ~let~ in here:
#+begin_src sml
fun find_largest (lst: real list) =
foldl (fn (elem, prev) => if elem > prev
then elem
else prev)
Real.negInf
lst;
#+end_src
* 3.4.5 - x^(2^i)
#+begin_src sml
fun expt2_expti (x, i) =
let
fun iter (acc, x, 0) = acc
| iter (acc, x, i) =
iter (acc * Math.pow (x, 2.0), x, i-1);
in
iter (1.0, x, i)
end;
expt2_expti (2.0, 4);
#+end_src
* 3.4.6 - alternative sum pairs
#+begin_src sml
fun sum_pairs nil = (0, 0)
| sum_pairs ((x, y)::zs) =
let
val (rest_odds_sum, rest_evens_sum) = sum_pairs zs;
in
(x + rest_odds_sum, y + rest_evens_sum)
end;
#+end_src
* 3.4.7 - sums of even and odd positions
#+begin_src sml
fun sum_even_odd nil = (0, 0)
| sum_even_odd (x::nil) = (x, 0)
| sum_even_odd (a::b::lst) =
let
val (a_next, b_next) = sum_even_odd lst;
in
(a + a_next, b + b_next)
end;
#+end_src
* 3.5.1 - concatenate lists
#+begin_src sml
fun cat (nil, nil) = nil
| cat (nil, lst2) = lst2
| cat (lst1, nil) = lst1
| cat (x::xs, ys) =
x :: cat (xs, ys);
#+end_src
* 3.5.2 - cycle - linear time
#+begin_src sml
(* WITH CONTINUATIONS *)
fun split_cycled_and_remaining (nil, count_to_take) = (nil, nil)
| split_up (lst, count_to_take) =
let
fun iter (nil, count_to_take, collect) = collect (nil, nil) (* PART1: Giving nil to the collector. *)
(* If there are still elements in the list ... *)
| iter ((x::xs), count_to_take, collect) =
(* ... and the list is supposed to be cycled by more elements ... *)
if count_to_take > 0
then
iter (xs,
count_to_take - 1,
(* + Wrap the collector in a new lambda expression, to
make a new collector.
+ The new collector uses the result of the old collector.
+ The old collector is given the arguments of the next
call, so that these are used before the current ones. *)
(fn (next_taken_elem, remaining_elems) =>
(* cons the current element in from of the result
from the previous collector *)
let
val (taken, rest) = collect (next_taken_elem, remaining_elems);
in
(* TODO: List is in wrong order. How to reverse without cost? *)
((x :: taken), rest)
end))
else
collect (nil, x::xs)
in
iter (lst,
count_to_take,
(* Initial continuation / collect function. This one will be the
last to be called. It will be wrapped by other lambdas during
processing the list. It being called last means, that one has
to give it nil, to finish building lists. See PART1.*)
(fn (taken, rest) => (taken, rest)))
end;
fun cycle (lst, 0) = lst
| cycle (nil, count) = nil
| cycle (lst, count) =
let
val (rev_cycle_elems, remaining) = split_cycled_and_remaining (lst, count);
in
remaining @ (rev rev_cycle_elems)
end;
(* OTHER SOLUTION *)
(* I found the following solution online at
, however, without
my comments, it is completely unreadable and ultimately it is not so great,
because it does unnecessary work. Made me lose some time figuring out, whether
this solution has any great insights, but apparently it has none. *)
fun cycle3 (nil, nil, ys) = ys
(* If there are no more reversed elements to be cycled, reverse the reversed
rest of the original list. This seems to be a bit of a silly step to do, as
they were only reversed in phase 2, to now be reversed again. >.<' *)
| cycle3 (x2r::x2rs, nil, ys) =
cycle3 (x2rs, nil, x2r::ys)
(* If there are more reversed elements to be cycled reverse them to correct
order and build up the resulting list. *)
| cycle3 (x2rs, x1r::x1rs, ys) = cycle3 (x2rs, x1rs, x1r::ys)
(* Phase 2: "Collect the rest of the original list."
Called as follows:
(arg 1) remaining elements of original list
(arg 2) initially empty list
(arg 3) accumulated elements, which shall be cycled *)
fun cycle2 (nil, x2rs, x1rs) =
(* If the original list has no more elements, go to phase 3.
Calling as follows:
(arg 1) reversed rest of original list
(arg 2) reversed elements to be cycled
(arg 3) initially empty list *)
cycle3 (x2rs, x1rs, nil)
(* If the original list has more elements, ... *)
| cycle2 (x2::x2s, x2rs, x1rs) =
(* ... accumulate them as well in reversed order, until no more elements are
left. At that point we have runtime of O(n) already. The algorithm cannot
have better worst case time complexity than O(n). *)
cycle2 (x2s, x2::x2rs, x1rs);
(* Phase 1: "Accumulate the elements to be cycled according to the counter and
original list." *)
fun cycle1 (x2s, x1rs, 0) =
(* If the number of to cycle elements has reached zero, enter the second
phase - The result of the first phase is, that all elements, which should
be cycled, are accumulated in reversed order in x1rs. *)
cycle2 (x2s, nil, x1rs)
| cycle1 (x::x2s, x1rs, n) =
(* If there are still elements in the list, which shall be cycled ... *)
(* ... cons the head of the original list onto the accumulated list. This
reverses the order of elements found in the original list. Continue with
the counter reduced by 1. *)
cycle1 (x2s, x::x1rs, n - 1)
| cycle1 (nil, x1rs, n) =
(* If there is no remaining element, but still elements should be cycled,
return the empty list. -- Is this a coorect idea? Why not cycle elements
more than once, if there are insufficient elements? Would that not be a
more natural cycling algorithm? *)
nil;
(*
,* x1s : list of elements to cycle
,* n : number of shifts to make
,*)
fun cycle (x1s, n) =
(* original list goes into the first slot *)
cycle1 (x1s, nil, n);
(* Considering, that I have not found a good solution online, I wonder, what the
actual by the author intended solution was. Did the exercise have 2 exclamation
marks, because of the way one might need to use continuations? Because of how it
involves multiple steps? Or did it have 2 exclamation marks, because the
solution is even more difficult to find, than the one with continuations? *)
#+end_src
* 3.6.* Polynomials
#+begin_src sml
structure Polynomial = struct
type CoefficientsList = real list;
fun add P nil = P
| add nil Q = Q
| add ((p:real)::ps) (q::qs) =
(p + q) :: (add ps qs);
fun scalar_multiply nil scalar = nil
| scalar_multiply ((p:real)::ps) scalar =
(p * scalar) :: (scalar_multiply ps scalar);
(* The coefficients of lowest exponents come first by
convention. Prepending a 0.0 will move all coefficients
to positions of coefficients of the next higher
exponents. *)
fun shift_increasing P = 0.0 :: P;
fun shift P 0 = P
| shift P n = shift_increasing (shift P (n - 1));
fun multiply P nil = nil
| multiply P (q::qs) =
add
(* Start calculating with the coefficient of the
lowest exponent. At the beginning, this will be
the coefficient for x^0. For x^0 only the
coefficient remains, because x^0 = 1. For later
iterations, the result will be shifted by 1
position to account for the higher exponent. *)
(scalar_multiply P q)
(*
The next iteration will create a result for the
next higher exponent. This fact is taken into
account here, by shifting the result of the
recursive call by 1 position, before adding it
to the complete result of the computation.
At each iteration, we increase the shift by 1,
which makes sense, because the list of
coefficients representing a polynomial is
complete from lowest exponent position to
highest exponent position. For example when we
multiply with the coefficient of x^1, the shift
will be 1. Then when we multiply with the
coefficient of x^2 the result will be shifted by
2. As a result we get the coefficients at the
correct positions.
,*)
(shift_increasing
(* Calculate the result for the coefficient
of the next exponent. *)
(multiply P qs));
fun substract P nil = P
| substract P Q =
add P (scalar_multiply Q ~1.0);
fun length P = List.length P;
end;
#+end_src
** Karatsuba-Ofman
There is some mathematical stuff in the book leading to the implementation of Karatsuba-Ofman algorithm.
#+begin_src sml
structure KaratsubaOfman = struct
exception UnsuitablePolynomial;
fun best_split n m =
(* If n is less than or equal to half of m, then use n. (Use the much smaller one.) *)
if 2 * n <= m then n
(* If m is less than or equal to half of n, then use m. (Use the much smaller one.) *)
else if 2 * m <= n then m
(* If n is less or equal to m, take half of m. *)
else if n <= m then m div 2
(* n/2 < m < n*)
else n div 2;
fun carve nil 0 = (nil, nil)
| carve nil n = raise UnsuitablePolynomial
| carve (P: Polynomial.CoefficientsList) 0 = (nil, P)
| carve ((p::ps): Polynomial.CoefficientsList) n =
let
val (qs,rs) = carve ps (n-1);
in
(p::qs, rs)
end;
fun karatsuba_ofman_multiply P nil = nil
| karatsuba_ofman_multiply nil Q = nil
| karatsuba_ofman_multiply P (q::nil) = Polynomial.scalar_multiply P q
| karatsuba_ofman_multiply (p::nil) Q = Polynomial.scalar_multiply Q p
| karatsuba_ofman_multiply P Q =
let
val n = Polynomial.length P;
val m = Polynomial.length Q;
val s = Polynomial.best_split n m;
val (T, U) = carve P s;
val (V, W) = carve Q s;
val TV = karatsuba_ofman_multiply T V;
val UW = karatsuba_ofman_multiply U W;
val TUVW = karatsuba_ofman_multiply (Polynomial.add T U) (Polynomial.add V W);
val middle = Polynomial.substract (Polynomial.substract TUVW TV) UW;
in
Polynomial.add
(Polynomial.add
TV
(Polynomial.shift middle s))
(Polynomial.shift UW (2*s))
end;
end;
#+end_src
** 3.6.1 - genPoly
#+begin_src sml
fun gen_poly 0 = nil
| gen_poly n =
1.0 :: (gen_poly (n - 1));
(* Differences start to be visible when making polynomials with 2000
coefficients. *)
KaratsubaOfman.karatsuba_ofman_multiply (gen_poly 1000) (gen_poly 1000);
Polynomial.multiply (gen_poly 2000) (gen_poly 2000);
#+end_src
** 3.6.2 - use naive multiply for low count of exponents
#+begin_src sml
fun karatsuba_ofman_multiply P nil = nil
| karatsuba_ofman_multiply nil Q = nil
| karatsuba_ofman_multiply P (q::nil) = Polynomial.scalar_multiply P q
| karatsuba_ofman_multiply (p::nil) Q = Polynomial.scalar_multiply Q p
| karatsuba_ofman_multiply P Q =
if (Polynomial.length P) + (Polynomial.length Q) < 4000
then
Polynomial.multiply P Q
else
let
val n = Polynomial.length P;
val m = Polynomial.length Q;
val s = Polynomial.best_split n m;
val (T, U) = carve P s;
val (V, W) = carve Q s;
val TV = karatsuba_ofman_multiply T V;
val UW = karatsuba_ofman_multiply U W;
val TUVW = karatsuba_ofman_multiply (Polynomial.add T U) (Polynomial.add V W);
val middle = Polynomial.substract (Polynomial.substract TUVW TV) UW;
in
Polynomial.add
(Polynomial.add
TV
(Polynomial.shift middle s))
(Polynomial.shift UW (2*s))
end;
#+end_src
** 3.6.3 - eval with value for x
#+begin_src sml
structure Polynomial = struct
type CoefficientsList = real list;
exception UnsuitablePolynomial;
fun add P nil = P
| add nil Q = Q
| add ((p:real)::ps) (q::qs) =
(p + q) :: (add ps qs);
fun scalar_multiply nil scalar = nil
| scalar_multiply ((p:real)::ps) scalar =
(p * scalar) :: (scalar_multiply ps scalar);
(* The coefficients of lowest exponents come first by
convention. Prepending a 0.0 will move all coefficients
to positions of coefficients of the next higher
exponents. *)
fun shift_increasing P = 0.0 :: P;
fun shift P 0 = P
| shift P n = shift_increasing (shift P (n - 1));
fun multiply P nil = nil
| multiply P (q::qs) =
add
(* Start calculating with the coefficient of the
lowest exponent. At the beginning, this will be
the coefficient for x^0. For x^0 only the
coefficient remains, because x^0 = 1. For later
iterations, the result will be shifted by 1
position to account for the higher exponent. *)
(scalar_multiply P q)
(*
The next iteration will create a result for the
next higher exponent. This fact is taken into
account here, by shifting the result of the
recursive call by 1 position, before adding it
to the complete result of the computation.
At each iteration, we increase the shift by 1,
which makes sense, because the list of
coefficients representing a polynomial is
complete from lowest exponent position to
highest exponent position. For example when we
multiply with the coefficient of x^1, the shift
will be 1. Then when we multiply with the
coefficient of x^2 the result will be shifted by
2. As a result we get the coefficients at the
correct positions.
,*)
(shift_increasing
(* Calculate the result for the coefficient
of the next exponent. *)
(multiply P qs));
fun substract P nil = P
| substract P Q =
add P (scalar_multiply Q ~1.0);
fun length P = List.length P;
fun eval nil x = raise UnsuitablePolynomial
| eval P (x:real) =
let
fun iter (nil, x, exponent: int) = 0.0
| iter ((p::ps), x, exponent: int) =
(p * Math.pow(x, (Real.fromInt exponent))) + iter(ps, x, (exponent + 1));
in
iter (P, x, 0)
end;
end;
#+end_src
** 3.6.4 - Polynomial roots
Given a list of coefficients, the polynomial is searched, which is the product of (x - coeff) for each coefficient. I do not understand why that product is the polynomial, whose root the polynomial of those coefficients is. Would not a "root" mean, that the resulting polynomial divided by one of the roots results in exactly the root again? As in square root of a polynomial? Perhaps the word "root" is used in a different sense here? Anyway, the book already gives the solution of how to calculate the "root" and that is what is implemented in the following:
#+begin_src sml
fun from_roots nil = 1.0
| from_roots (root::roots) =
(* Starting from lowest exponent of x, so the scalar is x^0 and x
is x^1, which means the substracted coefficient comes first. *)
Polynomial.multiply [~root, 1.0] (from_roots roots);
#+end_src
** 3.6.5 - Polynomials of Polynomials
This is about using polynomials of another variable (for example y) as coefficients for a polynomial (for example of x). For example:
1 + 2xy + 3xy^2 4(x^3)y
. This term can be written to make it easier to see the coefficients:
1 + 2xy + 3xy^2 + 4(x^3)y
= +1 + 2xy + 3xy^2 + 4(x^3)y | adding the + sign
= +1 + 2 xy + 3 xy^2 + 4(x^3)y | adding space for alignment
= +1(x^0) + 2(x^1)y + 3(x^1)y^2 + 4(x^3)y | adding x^n to make coefficients for the same exponents better visible
Now the polynomials of y become visible:
At position x^0: +1(x^0)
-> We are looking for a polynomial of "y", which results in a term with no more "y" in it.
-> ay^0 would result in a mere number.
-> ay^0 with value for "a" must result in 1.
Any value ^0 is 1, so that 1 needs to be multiplied with 1 to result in a 1.
-> The coefficient then is represented by: ~[1.0]~.
At position x^1: + 2(x^1)y + 3(x^1)y^2
-> We can take the x^1 outside: x^1 * (+2y +3y^2). The "y" containing term can be written completely as:
0y^0 + 2y^1 + 3y^2
-> The coefficient then is represented by: ~[0.0, 2.0, 3.0]~.
At position x^2: no term.
-> The coefficient then is represented by: ~[]~.
At position x^3: +4(x^3)y
The "y" containing term is +4y. It can be written completely as:
0y^0 +4y^1
-> The coefficient then is represented by: ~[0.0, 4.0]~.
#+begin_src sml
structure PolyPolynomial = struct
type CoeffList = real list;
type CoeffListList = CoeffList list;
exception UnsuitablePolyPolynomial;
fun add nil nil = nil
| add (PP: CoeffListList) nil = PP
| add nil (QQ: CoeffListList) = QQ
| add ((P:CoeffList)::Ps) ((Q:CoeffList)::Qs) =
(Polynomial.add P Q) :: (add Ps Qs);
(* Multiply a poly-polynomial with a polynomial. It is the
corresponding function to scalar multiplication for
polynomials. *)
fun polynomial_multiply nil polynomial = nil
| polynomial_multiply (P::Ps) polynomial =
(Polynomial.multiply P polynomial) :: (polynomial_multiply Ps polynomial);
(* Corresponding function to shift_increasing of
Polynomial. Instead of shifting by prepending a 0.0 to a list, we
shift by prepending nil, a list, to the list of lists of
coefficients.*)
fun shift_increasing PP = [] :: PP;
(* The function multiply is the same as multiply for
polynomials. Except that everything is one abstraction layer
higher. Instead of multiplying with a number as a coefficient, we multiply with *)
fun multiply nil nil = nil
| multiply PP nil = nil
| multiply nil QQ = nil
| multiply PP (Q::Qs) =
add
(polynomial_multiply PP Q)
(shift_increasing (multiply PP Qs));
end;
#+end_src
* Other code
:PROPERTIES:
:CUSTOM_ID: other-code
:END:
Perhaps this code should be put in a separate module.
** n choose k - summing smaller problems
#+begin_src sml
open IntInf;
fun n_choose_k (n: int, 1) = n
| n_choose_k (n: int, k: int) =
let
fun iter (n: int, k: int) =
if k = 0 orelse n = k
then 1
else
(* the number of possibilities without choosing one of the n
elements *)
iter (n - 1, k)
+
(* the number of possibilities with choosing one of the n
elements *)
iter (n - 1, k - 1);
in
if n >= k
then
iter (n, k)
else
raise Fail "n must be greater than or equal to k"
end;
#+end_src
** n choose k
#+begin_src sml
open IntInf;
fun n_choose_k (n: int, k: int) =
let
fun fac 0 = 1
| fac 1 = 1
| fac n =
let
fun iter 1 prod = prod
| iter remaining_factors prod =
iter (remaining_factors - 1) (prod * remaining_factors);
in
if n > 0
then iter n 1
else raise Fail "n must be 0 or greater"
end;
in
(fac n) div ((fac (n - k)) * (fac k))
end;
#+end_src
** reverse list
#+begin_src sml
fun reverse L =
let
fun iter (nil, M) = M
| iter (x::xs, ys) = iter (xs, x::ys)
in
iter (L, nil)
end;
#+end_src
** Printing
#+begin_src sml
fun print_list elem_2_str lst =
let
fun iter remaining_lst =
if (null remaining_lst)
then print ""
else
let
val _ = print (elem_2_str (hd remaining_lst));
val _ = print "\n";
in
iter (tl remaining_lst)
end;
in
iter lst
end;
print_list Int.toString [1,2,3,4]
#+end_src