Spring 2008
BMETKVIB422
|
|
Spring 2008 BMETKVIB422 |
|
This page contains information about the course held in English.
New exam date! Check below.
list([]). % The empty list is a list. list([_|L]) :- % A [Head|Tail] structure is a list if list(L). % Tail is a list.
length([], 0). % The empty list has 0 elements. length([_|L], X) :- % The length of a non-empty list is equal length(L, X1), % to the length of its tail X is X1 + 1. % plus one.
trlength([], X0, X0). % As L has no elements, X = X0. trlength([_|L], X0, X) :- % The sum of X0 and the length of the list is X1 is X0 + 1, % the same as the sum of X0+1 and the length trlength(L, X1, X). % of its tail.
length2(L, X) :- trlength(L, 0, X).
element([X|_], X). % X is the first element of L. element([_|Xs], X) :- % X is somewhere in the tail of L. element(Xs, X).
biggerelem([X1,X2|_], X2) :- % X is the second element of L X2 > X1. % and it is greater than the first element. biggerelem([_|Xs], X) :- % X is a suitable element later in the list. biggerelem(Xs, X).
biggerthansum(L, X) :- biggerthansum(L, 0, X).where biggerthansum(L, S, X) says that X is an element of L that's greater than S plus the sum of all the preceding elements (defined as zero if there are none).
biggerthansum([X|_], S, X) :- % X is a suitable element if it is the head X > S. % of the list and greater than S. biggerthansum([X1|Xs], S0, X) :- % X is a solution if it is also a solution of S1 is S0 + X1, % a reduced problem where the sum of the preceding biggerthansum(Xs, S1, X). % elements accounts for the head (X1) too.
listmax([X], X). % X is the only element of L, hence it is the greatest too. listmax([X1,X2|Xs], X) :- % L is at least two elements long, and X is the greatest element XM is max(X1,X2), % of the list we get from L by throwing away the smaller listmax([XM|Xs], X). % of the first two elements.
incprefix([], [], []). % If L has empty, so is L1 and L2. incprefix([X], [X], []). % If L has only one element, then it is an increasing list. incprefix([X1,X2|Xs], [X1], [X2|Xs]) :- % L1 contains only the first element of L X1 > X2. % If the second element of L is less than the first. incprefix([X1,X2|Xs], [X1|L1], L2) :- % If we prepend an element to a list that's X1 =< X2, % less than its head, then it will be prepended incprefix([X2|Xs], L1, L2). % to L1 in the solution.
fun fac 0 = 1 | fac n = n * fac (n-1)or
fun fac n = if n = 0 then 1
else n * fac (n-1)
or
fun fac n = case n of 0 => 1
| x => n * fac (n-1)
fun length [] = 0 | length (x::xs) = 1 + length xs
fun length2 [] n = n | length2 (x::xs) n = length2 xs (n+1)
fun maxl [x] = x
| maxl (x1::x2::xs) = if x1>x2 then maxl (x1::xs)
else maxl (x2::xs)
(*
firstWord' : char list -> char list -> char list * char list
remaining processed first unprocessed
characters characters word characters
*)
fun firstWord' [] cs = (rev cs, [])
| firstWord' (#" "::xs) cs = (rev cs, xs)
| firstWord' (x::xs) cs = firstWord' xs (x::cs)
(*
firstWord : char list -> char list * char list
characters first unprocessed
word characters
*)
fun firstWord cs = firstWord' cs []
(* words' : char list -> string list *)
fun words' [] = []
| words' ws =
let val (fw, rws) = firstWord ws
in implode fw :: words' rws
end
(* words : string -> string list *)
fun words s = words' (explode s)
(*
firstRamp' : int list -> int list -> int list * int list
remaining processed first unprocessed
numbers numbers ramp numbers
*)
fun firstRamp' [] r = (rev r, [])
| firstRamp' [x] r = (rev (x::r), [])
| firstRamp' (x1::x2::xs) r = if x1 < x2 then firstRamp' (x2::xs) (x1::r)
else (rev (x1::r), x2::xs)
(* We had no time to do the rest, but it's analogous to the previous one. *)
aseqs([], []). aseqs(L, [S|Ss]) :- L \= [], first_aseq(L, S, R), aseqs(R, Ss). first_aseq([], [], []). first_aseq([X], [X], []). first_aseq([X1, X2|Xs], S, R) :- D is X2-X1, first_aseq_aux([X1, X2|Xs], D, S, R). first_aseq_aux([X], _, [X], []). first_aseq_aux([X1, X2|Xs], D, [X1], [X2|Xs]) :- D =\= X2-X1. first_aseq_aux([X1, X2|Xs], D, [X1|S], R) :- D =:= X2-X1, first_aseq_aux([X2|Xs], D, S, R).
words([], []). words(L, [W|Ws]) :- L \= [], first_word(L, W, R), words(R, Ws). first_word([], [], []). first_word([32|S], [], S). first_word([C|S], [C|W], R) :- C \= 32, first_word(S, W, R).