nondeterministic choice implemented in different languages

choose.curry

{-# OPTIONS_FRONTEND -Wno-overlapping #-}

import AllSolutions

insert :: a -> [a] -> [a] -- warning: overlapping patterns = ndet
insert x xs     = x : xs
insert x (y:ys) = y : insert x ys

perm :: [a] -> [a]
perm []     = []
perm (x:xs) = insert x (perm xs)

sorted :: Ord a => [a] -> Bool
sorted [] = True
sorted [_] = True
sorted (x : ys@(y:_)) = x <= y && sorted ys

unisort :: Ord a => [a] -> [a]
unisort xs | sorted ch = ch
  where ch = perm xs

main :: IO ()
main = do
  -- a <- getAllValues $ perm [1, 2, 3]
  b <- getAllValues $ unisort [3, 1, 2] -- only 1 satisfiable solution
                                        -- nondeterminism completely removed
                                        -- using AllSolutions for monadic intf
  -- print a
  print b

choose.kk

infixr 00 (?)
infixr 60 (::)

effect amb
   ctl (?)(l : a, r : a) : a
   ctl fail() : a

val solutions =
  handler
    return(x)     -> [x]
    ctl fail()    -> []
    ctl (?)(l, r) -> resume(l) ++ resume(r)

fun tests()
  // FIXME
  /* this can be solved with using true/false for amb, then short-circuiting or thunking.
     either way we never execute the nested continuations more than once..
     but this kind of solution makes for a bad heavy-handed API compared to first-class logic langs */
  "Search space will be duplicated, unlike in logic langs".
    assert( solutions { 1 ? 2 ? 3 } == [1,2,1,3] )

fun main() solutions {
  [1,2,3].unisort
}

fun unisort(xs)
  val choice = xs.perm
  if choice.sorted
     then choice
     else fail()

fun perm(xs) match(xs)
  [] -> []
  Cons(y,ys) -> ys.perm.insert(y)

fun sorted(xs : list<int>) match (xs)
  [] -> True
  [_] -> True
  Cons(x, ys as Cons(y, _)) ->
    x <= y && sorted(ys)

fun insert(xs, x) match(xs)
  [] -> [x]
  Cons(y, ys) ->
    x :: xs ? y :: ys.insert(x)

fun (::)(x, xs) Cons(x, xs)

fun (==)(xs, ys) zipwith(xs, ys, (==)).all(id)

choose.pro

% swipl -g main

insert(X, XS, [X|XS]).
insert(X, [Y|YS], [Y|ZS]) :- insert(X, YS, ZS).

perm([], []).
perm([X|XS], YS) :- perm(XS, ZS), insert(X, ZS, YS).

sorted([]).
sorted([_]).
sorted([X,Y|YS]) :- X =< Y, sorted([Y|YS]).

unisort(XS, ZS) :- perm(XS, ZS), sorted(ZS).

main :- unisort([2,1,3], Out), write(Out).