[OCaml] Leniwe i gorliwe naprzemienne łączenie elementów z tablic

Odpowiedz Nowy wątek
2019-11-07 12:26
2

Zdefiniować funkcje polacz i lpolacz łączące naprzemiennie elementy dwóch list leniwych/gorliwych. Postać leniwa/gorliwa dotyczy też zwracanych wyników.

Na przykład:

[0;3;5;7;9;13] [2;4;6;8] zwraca [0;2;3;4;5;6;7;8;9;13]

W sposób gorliwy:

let rec polacz a b =
  match a with
  | [] -> b
  | x :: a' -> x :: polacz b a';;

polacz [-6;-5;-4] [1;2;3];;
polacz [] [1;2;3];;
polacz [1;2;3] [];;
polacz [5;4;3;2] [1;2;3;4;5;6];;

W sposób leniwy? Mam takie funkcje:

 type 'a llist = LNil | LCons of 'a * (unit -> 'a llist);; 
let rec lfrom k = LCons (k, function () -> lfrom (k+1));; // lfrom generuje ciąg kolejnych liczb całkowitych zaczynający się od k.
let rec toLazyList = function //ze zwykłej listy tworzy listę leniwą
[] -> LNil
| h::t -> LCons(h, function () -> toLazyList t);;
let rec ltake = function // ltake(n,xl) zwraca pierwszych n elementów listy leniwej xl w postaci zwykłej listy
(0, _) -> []
| (_, LNil) -> []
| (n, LCons(x,xf)) -> x::ltake(n-1, xf())
;;

Mam też konkatenację, skąd jest blisko do mojego rozwiązania, jednak nie wiem jak to przekształcić by realizowało moje zadanie.

 let rec (@$) ll1 ll2 =
match ll1 with
Lnil -> ll2
| LCons(x, xf) -> LCons(x, function () -> (xf()) @$ ll2);;
ltake(100, toLazyList[1;2;3] @$ toLazyList[7;8;9]);; //zwraca konkatenację

Chyba utknąłem w miejscu...

Pozostało 580 znaków

2019-11-07 12:53
1

Musisz zaimplementować funkcję merge z merge sort. Inaczej mówiąc porównujesz głowy i następnie dokonujesz odpowiedniego połączenia. W Elixirze na "zwykłych listach" to by było:

def merge(a, b), do: do_merge(a, b, [])

defp do_merge([], xb, acc), do: Enum.reverse(acc) ++ xb
defp do_merge(xa, [], acc), do: Enum.reverse(acc) ++ xa
defp do_merge([a | xa], [b | _] = xb, acc) when a < b, do: do_merge(xa, xb, [a | acc])
defp do_merge([a | _] = xa, [b | xb], acc), do: do_merge(xa, xb, [b | acc])

Pozostało 580 znaków

2019-11-07 13:18
0

A obydwa typy, lazy i eager, nie powinne mieć takiego samego interfejsu?


Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0