misc/recursion.erl at master · innaky/misc · GitHub

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
-module(recursion).
-export([fact/1, factmatch/1, my_length/1, tail_fact/1, tail_len/1]).
-export([repeat/2, tail_repeat/2, reverse/1, tail_reverse/1, tail_reverser/1, sublist/2, tail_sublist/2]).
-export([zip/2, tail_zip/2, partition/4, quicksort/1, my_map/2]).

fact(X) when X == 0 ->
    1;
fact(X) when X > 0 ->
    X * fact(X-1).

%% Factorial with pattern matching
factmatch(0) ->
    1;
factmatch(X) when X > 0 ->
    X * factmatch(X-1).

my_length([]) ->
    0;
my_length([_|T]) ->
    1 + my_length(T).

tail_fact(X) ->
    tail_fact(X,1).
tail_fact(0, Acc) ->
    Acc;
tail_fact(X,Acc) when X > 0 ->
    tail_fact(X-1, X*Acc).

tail_len(List) ->
    tail_len(List, 0).
tail_len([], Acc) ->
    Acc;
tail_len([_|T], Acc) ->
    tail_len(T, Acc+1).

repeat(_, Times) when Times == 0 ->
    [];
%% | is cons in Common lisp
repeat(Num, Times) ->
    [Num | repeat(Num, Times-1)].

tail_repeat(Num, Times) ->
    tail_repeat(Num, Times, []).
tail_repeat(_, Times, Acc) when Times == 0 ->
    Acc;
tail_repeat(Num, Times, Acc) ->
    tail_repeat(Num, Times-1, [Num|Acc]).

reverse([]) ->
    [];
reverse([H|T]) ->
    reverse(T)++[H].

tail_reverse(List) ->
    tail_reverse(List, []).
tail_reverse(List, Acc) when List == [] ->
    Acc;
tail_reverse([H|T], Acc) ->
    tail_reverse(T, [H|Acc]).

tail_reverser(List)->
    tail_reverser(List, []).
tail_reverser([], Acc) ->
    Acc;
tail_reverser([H|T],Acc) ->
    tail_reverser(T, [H|Acc]).

sublist(_, 0) ->
    [];
sublist([H|T], Num) when Num >= 0 ->
    [H]++sublist(T, Num-1).

tail_sublist(List, Num) ->
    tail_sublist(List, Num, []).
tail_sublist(_, 0, Acc) ->
    Acc;
tail_sublist([], _, Acc) ->
    Acc;
tail_sublist([H|T], Num, Acc) when Num > 0 ->
    tail_sublist(T, Num-1, Acc++[H]).

zip([], _) ->
    [];
zip(_, []) ->
    [];
zip([Hx|Tx], [Hy|Ty]) ->
    [{Hx, Hy}]++zip(Tx, Ty).

tail_zip(Flist, Slist) ->
    tail_zip(Flist, Slist, []).
tail_zip(_, [], Acc) ->
    Acc;
tail_zip([], _, Acc) ->
    Acc;
tail_zip([Hx|Tx], [Hy|Ty], Acc) ->
    [{Hx,Hy}]++tail_zip(Tx, Ty, Acc).

partition(_, [], Smaller, Larger) ->
    {Smaller, Larger};
partition(Pivot, [H|T], Smaller, Larger) ->
    if H >= Pivot ->
    partition(Pivot, T, [H|Smaller], Larger);
       H < Pivot ->
    partition(Pivot, T, Smaller, [H|Larger])
    end.

quicksort([]) ->
    [];
quicksort([Pivot|T]) ->
    {Smaller, Larger} = partition(Pivot, T, [], []),
    quicksort(Smaller) ++ [Pivot] ++ quicksort(Larger).

my_map(_, []) ->
    [];
my_map(F, [H|T]) ->
    [F(H) | my_map(F, T)].

%    (defun my-map (fn lst)
%      (if (equal lst nil)
%	  nil
%	  (cons (funcall fn (car lst))
%		(my-map fn (cdr lst)))))
%
%    (my-map #'(lambda (x)
%		(* x x)) '( 1 2 3))
%    => (1 4 9)