0

I've got this review question for one of my exams, and I need some guidance.

Using the following Prolog program as an executable specification,

mix(Xs,Ys):-remix(Xs,[],Ys).

remix([],Ys,Ys).    
remix([X|Xs],Ys,Zs):-remix(Xs,[X|Ys],Zs).

write an equivalent Haskell program.

This is what I have so far for the Haskell code:

mix Xs Ys = remix Xs [] Ys

remix [] Ys Zs = Zs

remix (X:Xs) Ys Zs = x : (remix Xs Ys Zs)

Is this Haskell program be equivalent to the Prolog code above? If not, what am I doing wrong?

false
  • 10,264
  • 13
  • 101
  • 209
Kumar
  • 33
  • 3
  • 2
    The Haskell programs have too many arguments. The last argument is typically regarded as the output in prolog, so in Haskell it should disappear. – chi Mar 23 '15 at 09:16
  • 2
    Also, all the names for Haskell parameters must be in _lowercase_. – chi Mar 23 '15 at 09:17
  • 3
    You cannot write an _equivalent_ Haskell program easily because Haskell has a different execution model. You can write a Haskell program that gives the same answers for a subset of the possible invocations of the Prolog program. –  Mar 23 '15 at 11:36

1 Answers1

2

The literal translation would be:

mix xs = remix xs []
remix [] ys = ys
remix (x:xs) ys = remix xs (x:ys)

Assuming that the first argument to mix/2 is strictly an input argument, and the last argument of both mix/2 and remix/3 are output argument. Then, the Haskell functions have as a return value the last argument of the Prolog predicates you are translating. Otherwise, the Haskell version is exactly the same as the Prolog, just correct Haskell syntax. Compare it to your attempt and you will see a lot of small differences (and I guess the Haskell compiler would tell you about these too?)

(Haskellers please correct me if this is wrong)

There are however some issues with this. The original Prolog program could be queried both ways:

?- mix([1,2,3], M).
M = [3, 2, 1].

?- mix(M, [3,2,1]).
M = [1, 2, 3] .

or even:

?- mix(X, Y), numbervars(X-Y, 0, _).
X = Y, Y = [] ;
X = Y, Y = [A] ;
X = [A, B],
Y = [B, A] ;
X = [A, B, C],
Y = [C, B, A] ;
X = [A, B, C, D],
Y = [D, C, B, A] . % and so on

However, the second query leaves a choice point, and if you try to see what other solutions you might get (type Space or ; instead of Enter), the program does not terminate. Does it say how the original Prolog program is meant to be used?

  • Being completely unfamiliar with Prolog, I guessed that `:-` must be a turnstile symbol, but it seems to go in the opposite direction. Strange. – dfeuer Mar 23 '15 at 14:59
  • @dfeuer Yes. `a(X) :- b(X, Y), c(X, Y).` means rather "`a(X)` is true when `b(X, Y)` is true, and `c(X, Y)` is also true". In "pretty-printed" code it is often represented by a short single arrow to the left. –  Mar 23 '15 at 15:12
  • 1
    FYI, there's a `logict` package for logic programming in Haskell, but I don't (yet) understand it at all. – dfeuer Mar 23 '15 at 15:15
  • @dfeuer Apparently, there is also miniKanren. There was a great answer some time ago by one of the authors: http://stackoverflow.com/questions/28467011/what-are-the-main-technical-differences-between-prolog-and-minikanren-with-resp –  Mar 23 '15 at 15:20
  • Thank you so much. This works. My implementation wasn't reversing the list as it was supposed to. Plus thank you for correcting my syntax. – Kumar Mar 23 '15 at 19:02