l3

Termin wykonania listy 3 to 25 / 28 października w zależności od wybranej grupy. Listę można oddać wcześniej.
   
Nie wolno stosować funkcji bibliotecznych (np. "length", "reverse", "append") o złożoności większej, niż O(1). W przypadku, gdy zachodzi konieczność ich użycia należy przygotować własną implementację.
Dla każdego programu przygotuj przynajmniej 3 testy przypadków skrajnych.
Implementacja Scala oraz Ocaml.

1) Napisz funkcję tworzącą z listy wejściowej dwie listy. W pierwszej mają się znaleźć wszystkie elementy o wartościach ujemnych, w drugiej - o wartościach dodatnich, nieparzystych (każda liczba ma spełniać oba te warunki). Porządek elementów musi być zachowany. Wynik zwróć w postaci pary list. Jaką złożoności obliczeniową i pamięciową udało Ci się osiągnąć?

   Przykład:
   wywołanie: splitBySign [-3;-6;7;-9;13]
   wynik    : ([-3;-6;-9],[7;13])

   Punkty: 5

2) Napisz funkcję zwracającą długość dowolnej listy. Funkcja ma mieć jeden parametr. Jaką złożoności obliczeniową i pamięciową udało Ci się osiągnąć?

   Przykład:
   wywołanie: lengthOfList [5;4;3;2]
   wynik    : 4

   Punkty: 2 

3) Napisz funkcję łączącą dwie podane listy. Elementy w liście wyjściowej mają występować naprzemiennie. Jaką złożoności obliczeniową i pamięciową udało Ci się osiągnąć? 

   Przykład:
   wywołanie: joinLists [5;4;3;2] [1;2;3;4;5;6]
   wynik    : [5;1;4;2;3;3;2;4;5;6]

   Punkty: 3 

Pomocniczo przypominam z poprzedniej listy różnice w definicjach:
https://www.journaldev.com/11930/scala-val-var-lazyval-def-constructs