Rekurze a akumulátory (functions are fun, part 3)

Za úkol je do příštího týdne vypracovat úkol 6c. Zadání je tomto odkazu (tam bude poslední verze se všemi opravami), popřípadě níže.

Doporučuji řešit i další úkoly, například úkoly 6d, které jsou vyloženě na akumulátory, úkoly 6g, a pro odvážné úkoly 6e a úkoly 6f. Samozřejmě za ty všechny dostanete příslušný počet bodů.

Na co při úkolu myslet

• někdy je výhodné použít akumulátory, jindy zase ne
• pro práci se seznamy používáme cases

Zadání

6c1

Může se hodit funkce string-explode. Vhodné pro procvičení akumulátorů.

fun encode(source :: String) -> List<{String; Number}>:
  doc: "Do a run-length-enconding of the string [source]."
  ...
where:
  encode("arr") is [list: {"a"; 1}, {"r"; 2}]
  encode("000101") is [list: {"0"; 3}, {"1"; 1}, {"0"; 1}, {"1"; 1}]
  encode("haaaaalooo") is [list: {"h"; 1}, {"a"; 5}, {"l"; 1}, {"o"; 3}]
end

Zajímavost: Podobně fungují některé komprimační algoritmy.

6c2

Vhodné pro procvičení akumulátorů.

fun group<T>(l :: List<Any>) -> List<List<T>>:
  doc: "Group consecutive items which are equal to each other into sublists"
  ...
where:
  group([list: "a", "a", "b"]) is [list: [list: "a", "a"], [list: "b"]]
  group(string-explode("aab")) is [list: [list: "a", "a"], [list: "b"]]
  group([list: 1, 1, 1, 2, 3, 1, 1])
    is [list: [list: 1, 1, 1], [list: 2], [list: 3], [list: 1, 1]]
end

6c3

fun flatten(l :: List<Any>) -> List<Any>:
  doc: "Merge all sublists in [l] into one 'flat' list (see the examples)"

  ...
where:
  flatten([list: 1, 2, 3]) is [list: 1, 2, 3]
  flatten([list: 1, 2, 3, [list: 1, 2, 3]]) is [list: 1, 2, 3, 1, 2, 3]
  flatten([list: 1, [list: 2, 2, 2, [list: 2.5, 2.9]], 3]) is [list: 1, 2, 2, 2, 2.5, 2.9, 3]
end