[Haskell-cafe] Re: Type-Level Naturals Like Prolog?
Tom.Schrijvers at cs.kuleuven.be
Wed Jul 19 03:55:02 EDT 2006
On Tue, 18 Jul 2006, Jared Warren wrote:
>> >> % defining natural numbers
>> >> natural(zero).
>> >> natural(s(X)) :- natural(X).
>> >> % translate to integers
>> >> toInt(zero, 0).
>> >> toInt(s(X), N) :- toInt(X, Y), N is Y + 1.
>> > Thank you. I can now more precisely state that what I'm trying to
>> > figure out is: what is 's', a predicate or a data structure? If it's a
>> > predicate, where are its instances? If not, what is the difference
>> > between the type language and Prolog such that the type language
>> > requires data structures?
>> it's data structure, to be exact, it's data constructor - just like,
>> for example, "Just" in Haskell. Haskell requires that all data
>> constructors should be explicitly defined before they can be used. you
>> can use "Just" to construct data values only if your program declares
>> "Just" as data constructor with "data" definition like this:
>> data Maybe a = Just a | Nothing
>> Prolog is more liberate language and there you can use any data
>> constructors without their explicit declarations, moreover, there is
>> no such declarations anyway
>> i once said you about good paper on type-classes level programming. if
>> you want, i can send you my unfinished article on this topic which shows
>> correspondences between logic programming, type classes and GADTs
> So predicates and data constructors have similar syntax but different
> semantics in Prolog?
That is right. The syntax and naming are different from Haskell though.
They are called respectively predicate and function symbols/functors, and
written like f(x1,...,xn) rather than F x1 ... xn. Terms are made of
possibly nested function symbols and variables, e.g.
f(f(f(a,X))) where f and a are used as function symbols
Atoms are made of a predicate symbol and terms,e.g.
p(f(f(f(a,X)))) where p is used as a predicate symbol
f and a are used as function symbols
Note that the same name can be used with multiple argument numbers and
both as a predicate and a function symbol.
> Say, for the sake of argument, if I wanted to do
> automatic translation, how would I tell which was which in a Prolog
Based on the syntax. Basically the top-level symbols are predicate symbols
and the nested ones are function symbols, e.g. in a clause
j(k) = l(m).
p, q and '=' are predicate symbols and all the rest are function symbols.
It's probably good to read a bit about it in a proper reference.
Wikipedia's Prolog entry lists a number of tutorials.
Department of Computer Science
tel: +32 16 327544
e-mail: tom.schrijvers at cs.kuleuven.be
More information about the Haskell-Cafe