Implementation of backtracking in Haskell

user_3294082 0
Viewed 124

Completely new to Haskell and I would appreciate some help.

Implementing predicates in Prolog that make use of some constraints that reduce the solution space so that the overall implementation is not a naive / brute force one is extremely easy. However now that I have to deal with Haskell I have no idea how to do this.

Given that at some point P1 I make a choice say A1 and at a later point in time P2 I make a choice say A2 that does not obey my constraint how can I go back to P1 and make a different choice in Haskell ?

I study Haskell for 2 days now and from what I've read this might be doable either by declaring a function inside a function or by using monads which I don't really understand and confuse me.

Could you please link me to / show me some simple Pick it - Leave it under constraints predicates that make use of backtracking -- preferably without monads -- so I can wrap my head around it?

backtracking recursion functional-programming haskell
1 Answers

Sure, here's a simple one that picks a number, then later if it discovers the number isn't even, it backs up and picks another.

searchForEven :: [Int] -> [Int]
searchForEven ns = [n | n <- ns, even n]

Here's an example that matches your described situation:

Given that at some point P1 I make a choice say A1 and at a later point in time P2 I make a choice say A2 that does not obey my constraint how can I go back to P1 and make a different choice?

p1 = [1..10]
p2 = [2,3,5,7]
constraint a b = a^2 + b^2 == 5^2

searchForPythagoreanTriple :: [Int]
searchForPythagoreanTriple =
    [ (a1, a2)
    | a1 <- p1
    , a2 <- p2
    , constraint a1 a2
    ]

I've used what I hope are fairly suggestive names to highlight how the example connects with the scenario you described.

And don't fear the monad. Look how identical it is in monad syntax:

searchForEven ns = do
    n <- ns
    guard (even n)
    pure n

searchForPythagoreanTriple = do
    a1 <- p1
    a2 <- p2
    guard (constraint a1 a2)
    pure (a1, a2)
user_7916040
Related