`grandfather person where person free`

at the KiCS2 prompt. KiCS2 then outputs all assignments to the `person` variable for which `grandfather person` is defined. For each of these assignments, it additionally prints the result of the expression `grandfather person`. Nondeterminism ============== Functions in Curry can actually be non-deterministic, that is, they can return multiple results. For example, we can define a function `element` that returns any element of a given list. To achieve this, we use overlapping patterns in our function definition. If several equations of a function definition match a particular function application, Curry takes all of them, not only the first one, as Haskell does. > element :: [el] -> el > element (el : _) = el > element (_ : els) = element els Now we can enter`element "Hello!"`

at the KiCS2 prompt, and the system outputs six different results. Logic programming ================= We have already seen how to combine functional and logic programming with Curry. Now we want to do pure logic programming. This means that we only want to search for variable assignments, but are not interested in expression results. If you are not interested in results, you typically use a result type with only a single value. Curry provides the type `Success` with the single value `success` for doing logic programming. Let us write some example code about routes between countries. We first introduce a type of some European and American countries. > data Country = Canada > | Estonia > | Germany > | Latvia > | Lithuania > | Mexico > | Poland > | Russia > | USA Now we want to define a relation called `borders` that tells us which country borders which other country. We implement this relation as a function of type`Country -> Country -> Success`

that has the trivial result `success` if the first country borders the second one, and has no result otherwise. Note that this approach of implementing a relation is different from what we do in functional programming. In functional programming, we use `Bool` as the result type and signal falsity by the result `False`. In Curry, however, we signal falsity by the absence of a result. Our `borders` relation only relates countries with those neighbouring countries whose names come later in alphabetical order. We will soon compute the symmetric closure of `borders` to also get the opposite relationships. > borders :: Country -> Country -> Success > Canada `borders` USA = success > Estonia `borders` Latvia = success > Estonia `borders` Russia = success > Germany `borders` Poland = success > Latvia `borders` Lithuania = success > Latvia `borders` Russia = success > Lithuania `borders` Poland = success > Mexico `borders` USA = success Now we want to define a relation `isConnected` that tells whether two countries can be reached from each other via a land route. Clearly, `isConnected` is the equivalence relation that is generated by `borders`. In Prolog, we would write clauses that directly express this relationship between `borders` and `isConnected`. In Curry, on the other hand, we can write a function that generates an equivalence relation from any given relation and therefore does not only work with `borders`. We first define a type alias `Relation` for the sake of convenience. > type Relation val = val -> val -> Success Now we define what reflexive, symmetric, and transitive closures are. > reflClosure :: Relation val -> Relation val > reflClosure rel val1 val2 = rel val1 val2 > reflClosure rel val val = success > > symClosure :: Relation val -> Relation val > symClosure rel val1 val2 = rel val1 val2 > symClosure rel val2 val1 = rel val1 val2 > > transClosure :: Relation val -> Relation val > transClosure rel val1 val2 = rel val1 val2 > transClosure rel val1 val3 = rel val1 val2 & > transClosure rel val2 val3 > > where val2 free The operator `&` used in the definition of `transClosure` has type`Success -> Success -> Success`

and denotes conjunction. We define the function for generating equivalence relations as a composition of the above closure operators. Note that it is crucial that the transitive closure operator is applied after the symmetric closure operator, since the symmetric closure of a transitive relation is not necessarily transitive. > equivalence :: Relation val -> Relation val > equivalence = reflClosure . transClosure . symClosure The implementation of `isConnected` is now trivial. > isConnected :: Country -> Country -> Success > isConnected = equivalence borders Now we let KiCS2 compute which countries I can reach from Estonia without a ship or plane. We do so by entering``Estonia `isConnected` country where country free``

at the prompt. We can also implement a nondeterministic function that turns a country into the countries connected to it. For this, we use a guard that is of type `Success`. Such a guard succeeds if it has a result at all, which can only be `success`, of course. > connected :: Country -> Country > connected country1 > | country1 `isConnected` country2 = country2 > > where country2 free Equational constraints ====================== Curry has a predefined operator`=:= :: val -> val -> Success`

that stands for equality. We can use this operator, for example, to define a nondeterministic function that yields the grandchildren of a given person. Again, we keep things simple by only considering relationships that solely go via fathers. > grandchild :: Person -> Person > grandchild person > | grandfather grandkid =:= person = grandkid > > where grandkid free Note that `grandchild` is the inverse of `grandfather`. Functional patterns =================== Functional patterns are a language extension that allows us to use ordinary functions in patterns, not just data constructors. Functional patterns are implemented by KiCS2. Let us look at an example again. We want to define a function `split` that nondeterministically splits a list into two parts.[^split] Without functional patterns, we can implement splitting as follows. [^split]: Note that our `split` function is not the same as the `split` function in Curry’s `List` module. > split' :: [el] -> ([el],[el]) > split' list | front ++ rear =:= list = (front,rear) > > where front, rear free With functional patterns, we can implement splitting in a much simpler way. > split :: [el] -> ([el],[el]) > split (front ++ rear) = (front,rear) As a second example, let us define a function `sublist` that yields the sublists of a given list. > sublist :: [el] -> [el] > sublist (_ ++ sub ++ _) = sub Inverting functions =================== In the `grandchild` example, we showed how we can define the inverse of a particular function. We can go further and implement a generic function inversion operator. > inverse :: (val -> val') -> (val' -> val) > inverse fun val' | fun val =:= val' = val where val free With this operator, we could also implement `grandchild` as `inverse grandfather`. Inverting functions can make our lives a lot easier. Consider the example of parsing. A parser takes a string and returns a syntax tree. Writing a parser directly is a non-trivial task. However, generating a string from a syntax tree is just a simple functional programming exercise. So we can implement a parser in a simple way by writing a converter from syntax trees to strings and inverting it. We show this for the language of all arithmetic expressions that can be built from addition, multiplication, and integer constants. We first define types for representing abstract syntax trees. These types resemble a grammar that takes precedence into account. > type Expr = Sum > > data Sum = Sum Product [Product] > data Product = Product Atom [Atom] > data Atom = Num Int | Para Sum Now we implement the conversion from abstract syntax trees to strings. > toString :: Expr -> String > toString = sumToString > > sumToString :: Sum -> String > sumToString (Sum product products) > = productToString product ++ > concatMap ((" + " ++) . productToString) products > > productToString :: Product -> String > productToString (Product atom atoms) > = atomToString atom ++ > concatMap ((" * " ++) . atomToString) atoms > > atomToString :: Atom -> String > atomToString (Num num) = show num > atomToString (Para sum) = "(" ++ sumToString sum ++ ")" Implementing the parser is now extremely simple. > parse :: String -> Expr > parse = inverse toString KiCS2 uses a depth-first search strategy by default. However, our parser implementation does not work with depth-first search. So we switch to breadth-first search by entering`:set bfs`

at the KiCS2 prompt. Now we can try out the parser by entering`parse "2 * (3 + 4)"` .