is_list([]) => true.
is_list([_|T]) => is_list(T).

my_first([H|_]) = H.

my_last([X]) = X.
my_last([_|T]) = my_last(T).

contains([E|_],E) => true.
contains([_|T],E) => contains(T,E).

find_first_of(L,E) = find_first_of(L,E,1).

find_first_of([E|_],E,I) = I.
find_first_of([_|T],E,I) = find_first_of(T,E,I+1).
find_first_of([],_E,_I) = -1.

find_last_of(L,E) = find_last_of(L,E,1,-1).

find_last_of([],_E,_I,PreI) = PreI.
find_last_of([E|T],E,I,_PreI) = find_last_of(T,E,I+1,I).
find_last_of([_|T],E,I,PreI) = find_last_of(T,E,I+1,PreI).

% the kth_elm(L,K) is the same as L[K]
kth_elm([E|_],1) = E.
kth_elm([_|T],K) = kth_elm(T,K-1).

naive_reverse([]) = [].
naive_reverse([H|T]) = naive_reverse(T) ++ [H].

sorted([]) => true.
sorted([_]) => true.
sorted([X,Y|L]) =>
    X @=< Y,
    sorted([Y|L]).

my_len(L) = sum([1 : _ in L]).

my_len2(L) = Len =>
    Count = 0,
    foreach (_ in L)
        Count := Count+1
    end,
    Len = Count.

my_len3([]) = 0.
my_len3([_|T]) = my_len3(T)+1.

my_len4(L) = Len => my_len4(L,0,Len).

my_len4([],Len0,Len) => Len = Len0.
my_len4([_|T],Len0,Len) =>
    my_len4(T,Len0+1,Len).

triplets([X,Y,Z|L]) = [[X,Y,Z]|triplets(L)].
triplets(L) = [L].

has_duplicate_key(L) =>   
    S = new_set(),
    has_duplicate_key(L,S).

has_duplicate_key([],_S) => fail.
has_duplicate_key([(Key,_)|L],S) =>
    if S.has_key(Key) then
        true
    else
        S.put(Key),
        has_duplicate_key(L,S)
    end.

send_more_money =>
    Vars=[S,E,N,D,M,O,R,Y],
    generate(Vars,0..9),
    S != 0,
    M != 0,
    1000*S+100*E+10*N+D+1000*M+100*O+10*R+E
    = 10000*M+1000*O+100*N+10*E+Y,
    println(Vars).

generate([],_D) => true.
generate([Var|Vars],D) =>
     select(Var,D,RestD),
     generate(Vars,RestD).

is_btree(nil) => true.
is_btree({_,Left,Right}) =>
     is_btree(Left),
     is_btree(Right).

inorder(nil) = [].
inorder({Root,Left,Right}) = inorder(Left) ++ 
                             [Root] ++ 
                             inorder(Right).
count_nodes(nil) = 0.
count_nodes({_,Left,Right}) = count_nodes(Left) +
                              count_nodes(Right) + 1.

% test if a given tree is a binary search tree
is_bstree(T) => is_bstree(T,minint_small(),maxint_small()).

is_bstree(nil,_Min,_Max) => true.
is_bstree({Root,Left,Right},Min,Max) =>
    Min =< Root,
    Root < Max,
    is_bstree(Left,Min,Root),
    is_bstree(Right,Root,Max).

main =>
    T = {a, {b, {d, nil,nil},
                {e, nil,nil}
             },
             {c, nil,nil}
          },
     println(inorder(T)).