Is there a functional programming language with Prolog style unification?

Suppose that I’m pattern matching in SML or Haskell. The pattern matching can only go “one way”. Prolog, however, peforms a full unification on all patterns. For instance, if Haskell had unification, a function like this could be possible:



data BinaryTree a = Empty | Node left contents right

member :: BinaryTree a -> a -> Bool
member Empty item = false
member (Node left item right) item = true
member (Node left not_item right) item = member(left) or member(right)


Is there a functional programming language that performs unification?

Of course, the last line of my function declaration should be:



member (Node left not_item right) item = (member left item) or (member right item)


:smack:

Howdy, Dominic Mulligan,

You probably don’t know me. I’m Mbossa, resident Haskell nut. Few people have needed my help until now.

I’m not too familiar with any functional languages apart from Haskell. I don’t know the answer to this exact question, but I was planning on spending a part of this (New Zealand) evening finding out exactly why Haskell doesn’t support this. Unfortunately, my friend rang me and told me to get drunk with him this evening, so I did. It’s now about 4:30am, and I am rather drunk and I need to go to work fairly early tomorrow, so I can’t give you any information at this point in time.

However, I can tell you that your code is still not quite correct. It should be something like this:



data BinaryTree a = Empty | Node (BinaryTree a) a (BinaryTree a)

member :: BinaryTree a -> a -> Bool
member Empty item = False
member (Node left item right) item = True
member (Node left not_item right) item = (member left item) || (member right item)


Boolean values should have initial uppercase characters, the type declaration needs more information about structure, and the ‘or’ operator is C-style

As I say, I’m too drunk to help you on your question right now. However, I can point you to the Haskell mailing lists which give you links to archives you can scan through: http://www.haskell.org/mailinglist.html. But I’m hoping I can give you a better answer to your question tomorrow, because now you’ve made me curious.

If you need any help on Haskell in particular, be sure to page me – I do pointless vanity searches fairly often and it would be nice to have one that’s not so pointless. I’ve always dreamed about teaching a fellow doper about IO in Haskell.

If any of this post is incorrect and/or rambling, you can blame my present drunkeness that I’ve mentioned a few times.

I’m not familiar with any languages that do full Prolog-style unification except, well, Prolog. The best you can probably get is one of those Prolog-embedded-in-Lisp deals, which may or may not do what you want.

At a guess, the ML derivatives all avoid this feature because of their type system. The type resolution algorithm is very fragile, so it’s hard to add features to it without accidentally making the algorithm exponential. I’ll ask my programming languages prof about this if I can catch him.

I asked the same question on another board, too.

Apparently there’s a language called Curry which is a cross between a logic programming language and a functional one which does unification. Common Lisp also does it with the aid of a language extension, apparently.

I’m still very new to Haskell, so there were bound to be some mistakes that slipped through :smack:

Thanks for the help, both of you.

You might want to look at Poplog, which is a funky, funky language. From the website:

Your a New Zealander and a Haskell nut? Damn, I wish I knew this before I just returned from New Zealand yesterday. I might be in Nelson in February though for a conference, maybe we could catch up for a beer or something.

BTW: Do you know Manuel Chakravarty? He’s reputadly one of the top 10 most knowledgable people about Haskell on the planet and I had the pleasure of taking one of his courses.

If you want a less funky (but much more expensive) solution, check out the Enterprise Edition of Lispworks (www.lispworks.com). It includes Knowledgeworks, a Prolog-in-Lisp (plus a lot more) type system. I’ve used it, and had a favorable impression.

Thanks all for the recommendations.