List edit distance

Máte zadány dva seznamy porovnatelných prvků a chcete zjistit, v kolika krocích budete umět z toho prvního vyrobit ten druhý — tzv. edit distance. V každém kroku buďto

1. Přidáme jeden prvek (Add)
2. Vymažeme jeden prvek (Del)
3. Změníme jeden prvek na jiný (Mod)

Pokud tedy například budeme chtít změřit edit distance mezi seznamy [1, 2, 3] a [-10, 3], ptáme se vlastně, kolik nejméně výše zmíněných kroků musíme udělat, abychom z [1, 2, 3] vyrobili [-10, 3]. V tomto případě nám stačí dva kroky:

1. Del (vymaže jedničku, implicitně nás tedy "posune" na další prvek a koukáme teď na 2)
2. Mod -10 (změní 2 na -10)

Edit distance těchto seznamů je tedy 2.

Založení projektu (opakování)

1. Nová složka
2. Otevřít složku ve VS Code
3. Spustit spago init
4. Spustit spago build
   • (případně) Nainstalovat potřebné balíčky pomocí spago install
   • Vždy po spago install spustit ručně opět spago build
5. Hrát si s kódem ve spago repl

Úroveň 1 (10 bodů)

Spočítejte edit distance dvou zadaných seznamů. Neřešte zatím efektivitu.

> import Data.List
> editDistance (1:2:3:Nil) (-10:3:Nil)
2
> :type editDistance
forall a. Eq a =>  List a -> List a -> Int

Úroveň 2 (15 + 15 bodů)

Napište novou funkci, která bude kromě edit distance vracet i posloupnost operací, pomocí kterých lze z prvního seznamu vyrobit druhý, tzv. edit script. Na operace si udělejte vhodný datový typ Operation, který kromě výše zmíněných operací bude podporovat i None, tj. operaci značící "zde byla mezi seznamy shoda, nedělej nic". Tento None se nepočítá do celkové edit distance.

Celá funkce bude mít typ editScript :: forall a. Eq a => List a -> List a -> Tuple Int (List (Operation a))

> editScript (1:2:3:Nil) (-10:3:Nil)
Tuple 2 (Del : Mod -10 : None)
> editScript (1:10:Nil) (1:1:1:1:Nil)
Tuple 3 (None : Mod : Add 1 : Add 1 )

Zkuste také napsat funkci runScript :: forall a. Eq a => List a -> List (Operation a) -> Maybe (List a), která dostane skript, "supstí ho" a vrátí výsledný seznam. Případy, kdy vám uživatel dá nesprávný skript (tj. skript, který na vstupním seznamu nefunguje), řeště tím, že vrátíte Nothing.