Een laatste variant van onze interpreter bestaat eruit deze zodanig aan te passen dat in de plaats van één enkel antwoord hij een verzameling van antwoorden zal teruggeven.

Hiervoor breiden we de taal uit met een nieuwe primitieve Amb die aangeeft dat een waarde een van twee termen is. Bijvoorbeeld Amb (Con 5) (Con 3) is een expressie die niet-deterministisch de waarde 5 of 3 zal zijn. Om een expressie met bijvoorbeeld 3 mogelijke waarden voor te stellen, kan je Amb recursief herhalen. We voegen ook de taalconstructie Fail toe die aangeeft dat er geen enkele mogelijk waarde is. Een voorbeeldprogramma is hieronder weergegeven:

> test $ App (Lam "x" (Add (Var "x") (Var "x"))) (Amb (Con 1) (Con 2))
"2 of 4"
> test $ Fail
"Fail"

We schrijven ook een extra functie, plusL, die toestaat om 2 verzamelingen aan antwoorden samen te voegen.

Het is aan jou om een geschikte monad te vinden en de nodige aanpassingen te maken.