hit counter

Timeline

My development logbook

Ex 2.2

Exercise 2.2 (Andersson [And91D]) In the worst case, member performs approximately 2d comparisons, where d is the depth of the tree. Rewrite member to take no more than d + 1 comparisons by keeping track of a candidate element that might be equal to the query element (say, the last element for which < returned false or < returned true) and checking for equality only when you hit the bottom of the tree.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
-module(ex2_2).
-export([make_sample_tree/0, test_insert/0]).

-record(treenode, {key, value}).
-record(tree, {left, treenode=#treenode{}, right}).

make_node(K, V) ->
    TN = #treenode{key=K, value=V},
    T = #tree{treenode=TN},
    T.

make_node(K, V, LeftTree, RightTree) ->
    TN = #treenode{key=K, value=V},
    T = #tree{treenode=TN, left=LeftTree, right=RightTree},
    T.

insert_tree_node(undefined, K, V) ->
    make_node(K, V);
insert_tree_node(#tree{left=LT, treenode=#treenode{key=CurK, value=_CurV}, right=_RT}=T, K, V) when K < CurK  ->
    LT1=insert_tree_node(LT, K, V),
    T1=T#tree{left=LT1},
    T1;
insert_tree_node(#tree{left=_LT, treenode=#treenode{key=CurK, value=_CurV}, right=RT}=T, K, V) when K > CurK  ->
    RT1=insert_tree_node(RT, K, V),
    T1=T#tree{right=RT1},
    T1;
% when K == CurK
insert_tree_node(T, _K, V)  when is_record(T, tree) ->
    T#tree{treenode=#treenode{value=V}}.

%% routines for testings
%% 
make_sample_tree() ->
    Left = make_node(1, 1),
    Right = make_node(5, 5),
    T = make_node(3, 3, Left, Right),
    T.

test_insert() ->
    T = make_sample_tree(),
    T1 = insert_tree_node(T, 7, 7),
    io:format("old ~p~n", [T]),
    io:format("new ~p~n", [T1]).

Ex 2.1

Exercise 2.1 Write a function suffixes of type a list –> a list of list that takes a list xs and returns a list of all the suffixes of xs in decreasing order of length. For example,

suffixes [1,2,3,4] = [[1,2,3,4], [2,3,4], [3,4], [4], [ ] ]

Show that the resulting list of suffixes can be generated in O(n) time and rep- resented in O(n) space.

1
2
3
4
5
6
7
8
9
-module(e2_1).

-export([suffixes/1]).

suffixes(L) -> suffixes(L, []).

suffixes([H|T], R)
    -> suffixes(T, [[H|T]|R]);
suffixes([], R) -> lists:reverse([[]|R]).

Html vs Xhtml

HTML is not case-sensitive but XHTML is

Install Mirage Failed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[ERROR] Due to some errors while processing optcomp.1.6, the following actions will NOT proceed:
 - install mirage.1.1.3
 - install ocplib-endian.0.7
 - install io-page.1.1.1
 - install mirage-types.1.1.3
 - install cstruct.1.3.0

===== ERROR while installing optcomp.1.6 =====
Could not get the source for optcomp.1.6:
# opam-version    1.1.1
# os              linux
Cannot download https://opam.ocaml.org/archives/optcomp.1.6+opam.tar.gz, please check your connection settings.

The former state can be restored with opam switch import -f "/home/antkong/.opam/system/backup/state-20140606112154.export"
'opam install mirage' failed.