From 6af96f1c5eb9bca79b8b8751f8f2d7292f959a75 Mon Sep 17 00:00:00 2001 From: Robert Peterson Date: Wed, 17 Apr 2019 10:33:42 -0700 Subject: Add list:intersperse list:at list:unique list:sort --- gen/src/list.erl | 75 +++++++++++++++++++++++++++++++++++++++++++++++++- gen/test/list_test.erl | 24 +++++++++++++++- src/list.gleam | 54 ++++++++++++++++++++++++++++++++++++ test/list_test.gleam | 47 +++++++++++++++++++++++++++++++ 4 files changed, 198 insertions(+), 2 deletions(-) diff --git a/gen/src/list.erl b/gen/src/list.erl index 39a30a3..10a093a 100644 --- a/gen/src/list.erl +++ b/gen/src/list.erl @@ -1,7 +1,7 @@ -module(list). -compile(no_auto_import). --export([length/1, reverse/1, is_empty/1, contains/2, head/1, tail/1, filter/2, map/2, traverse/2, drop/2, take/2, new/0, append/2, flatten/1, fold/3, fold_right/3, find/2, all/2, any/2, zip/2]). +-export([length/1, reverse/1, is_empty/1, contains/2, head/1, tail/1, filter/2, map/2, traverse/2, drop/2, take/2, new/0, append/2, flatten/1, fold/3, fold_right/3, find/2, all/2, any/2, zip/2, intersperse/2, at/2, unique/1, sort/1]). length(A) -> erlang:length(A). @@ -213,3 +213,76 @@ zip(L1, L2) -> {[X1 | Rest1], [X2 | Rest2]} -> [{X1, X2} | zip(Rest1, Rest2)] end. + +intersperse(List, Elem) -> + case List of + [] -> + []; + + [X] -> + [X]; + + [X1 | Rest] -> + [X1, Elem | intersperse(Rest, Elem)] + end. + +at(List, I) -> + case I < 0 of + true -> + {error, not_found}; + + false -> + case List of + [] -> + {error, not_found}; + + [X | Rest] -> + case I =:= 0 of + true -> + {ok, X}; + + false -> + at(Rest, I - 1) + end + end + end. + +unique(List) -> + case List of + [] -> + []; + + [X | Rest] -> + [X | unique(filter(Rest, fun(Y) -> Y /= X end))] + end. + +merge_sort(A, B) -> + case {A, B} of + {[], _} -> + B; + + {_, []} -> + A; + + {[Ax | Ar], [Bx | Br]} -> + case Ax < Bx of + true -> + [Ax | merge_sort(Ar, B)]; + + false -> + [Bx | merge_sort(A, Br)] + end + end. + +sort(List) -> + ListLength = length(List), + case ListLength < 2 of + true -> + List; + + false -> + SplitLength = ListLength div 2, + AList = take(List, SplitLength), + BList = drop(List, SplitLength), + merge_sort(sort(AList), sort(BList)) + end. diff --git a/gen/test/list_test.erl b/gen/test/list_test.erl index 9cb1ac3..6105a88 100644 --- a/gen/test/list_test.erl +++ b/gen/test/list_test.erl @@ -1,7 +1,7 @@ -module(list_test). -compile(no_auto_import). --export([length_test/0, reverse_test/0, is_empty_test/0, contains_test/0, head_test/0, tail_test/0, filter_test/0, map_test/0, traverse_test/0, drop_test/0, take_test/0, new_test/0, append_test/0, flatten_test/0, fold_test/0, fold_right_test/0, find_test/0, all_test/0, any_test/0, zip_test/0]). +-export([length_test/0, reverse_test/0, is_empty_test/0, contains_test/0, head_test/0, tail_test/0, filter_test/0, map_test/0, traverse_test/0, drop_test/0, take_test/0, new_test/0, append_test/0, flatten_test/0, fold_test/0, fold_right_test/0, find_test/0, all_test/0, any_test/0, zip_test/0, intersperse_test/0, at_test/0, unique_test/0, sort_test/0]). length_test() -> expect:equal(list:length([]), 0), @@ -110,3 +110,25 @@ zip_test() -> expect:equal(list:zip([1, 2, 3], [4, 5, 6]), [{1, 4}, {2, 5}, {3, 6}]), expect:equal(list:zip([5, 6], [1, 2, 3]), [{5, 1}, {6, 2}]), expect:equal(list:zip([5, 6, 7], [1, 2]), [{5, 1}, {6, 2}]). + +intersperse_test() -> + expect:equal(list:intersperse([1, 2, 3], 4), [1, 4, 2, 4, 3]), + expect:equal(list:intersperse([], 2), []). + +at_test() -> + expect:equal(list:at([1, 2, 3], 2), {ok, 3}), + expect:is_error(list:at([1, 2, 3], 5)), + expect:is_error(list:at([], 0)), + expect:is_error(list:at([1, 2, 3, 4, 5, 6], -1)). + +unique_test() -> + expect:equal(list:unique([1, 1, 2, 3, 4, 4, 4, 5, 6]), [1, 2, 3, 4, 5, 6]), + expect:equal(list:unique([7, 1, 45, 6, 2, 47, 2, 7, 5]), + [7, 1, 45, 6, 2, 47, 5]), + expect:equal(list:unique([3, 4, 5]), [3, 4, 5]), + expect:equal(list:unique([]), []). + +sort_test() -> + expect:equal(list:sort([4, 3, 6, 5, 4]), [3, 4, 4, 5, 6]), + expect:equal(list:sort([]), []), + expect:equal(list:sort([{1, 2}, {4, 5}, {3, 2}]), [{1, 2}, {3, 2}, {4, 5}]). diff --git a/src/list.gleam b/src/list.gleam index 5ea2ee3..5aa1e8e 100644 --- a/src/list.gleam +++ b/src/list.gleam @@ -184,3 +184,57 @@ pub fn zip(l1, l2) { | {[x1 | rest1], [x2 | rest2] } -> [ {x1, x2} | zip(rest1, rest2) ] } } + +pub fn intersperse(list, elem) { + case list { + | [] -> [] + | [x | []] -> [x] + | [x | rest] -> [x | [elem | intersperse(rest, elem)]] + } +} + +pub fn at(list, i) { + case i < 0 { + | True -> Error(NotFound) + | False -> + case list { + | [] -> Error(NotFound) + | [x | rest] -> + case i == 0 { + | True -> Ok(x) + | False -> at(rest, i - 1) + } + } + } +} + +pub fn unique(list) { + case list { + | [] -> [] + | [x | rest] -> [x | unique(filter(rest, fn(y) { y != x }))] + } +} + +fn merge_sort(a, b) { + case {a, b} { + | {[], _} -> b + | {_, []} -> a + | {[ax | ar], [bx | br]} -> + case ax < bx { + | True -> [ax | merge_sort(ar, b)] + | False -> [bx | merge_sort(a, br)] + } + } +} + +pub fn sort(list) { + let list_length = length(list) + case list_length < 2 { + | True -> list + | False -> + let split_length = list_length / 2 + let a_list = take(list, split_length) + let b_list = drop(list, split_length) + merge_sort(sort(a_list), sort(b_list)) + } +} diff --git a/test/list_test.gleam b/test/list_test.gleam index e7cd786..f9882c0 100644 --- a/test/list_test.gleam +++ b/test/list_test.gleam @@ -201,3 +201,50 @@ pub fn zip_test() { list:zip([5,6,7], [1,2]) |> expect:equal(_, [{5,1}, {6,2}]) } + +pub fn intersperse_test() { + list:intersperse([1,2,3], 4) + |> expect:equal(_, [1,4,2,4,3]) + + list:intersperse([], 2) + |> expect:equal(_, []) +} + +pub fn at_test() { + list:at([1,2,3], 2) + |> expect:equal(_, Ok(3)) + + list:at([1,2,3], 5) + |> expect:is_error + + list:at([], 0) + |> expect:is_error + + list:at([1,2,3,4,5,6], -1) + |> expect:is_error +} + +pub fn unique_test() { + list:unique([1,1,2,3,4,4,4,5,6]) + |> expect:equal(_, [1,2,3,4,5,6]) + + list:unique([7,1,45,6,2,47,2,7,5]) + |> expect:equal(_, [7,1,45,6,2,47,5]) + + list:unique([3,4,5]) + |> expect:equal(_, [3,4,5]) + + list:unique([]) + |> expect:equal(_, []) +} + +pub fn sort_test() { + list:sort([4,3,6,5,4]) + |> expect:equal(_, [3,4,4,5,6]) + + list:sort([]) + |> expect:equal(_, []) + + list:sort([{1,2}, {4,5}, {3,2}]) + |> expect:equal(_, [{1,2}, {3,2}, {4,5}]) +} -- cgit v1.2.3