Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Church Numerals in haskell

I am trying to print church numerals in haskell using the definions:

0 := λfx.x
1 := λfx.f x

Haskell code:

c0 = \f x -> x
c1 = \f x -> f x

When I enter it in the haskell console I get an error which says

    test> c1

    <interactive>:1:0:
    No instance for (Show ((t -> t1) -> t -> t1))
      arising from a use of `print' at <interactive>:1:0-1
    Possible fix:
      add an instance declaration for (Show ((t -> t1) -> t -> t1))
    In a stmt of an interactive GHCi command: print it

I am not able to exactly figure out what error says.

Thank you!

like image 812
Bharat Avatar asked Jun 24 '11 02:06

Bharat


1 Answers

The problem here is that, by default, it's not possible to print values in Haskell. The default way to print things--used by the print function and by the GHCi REPL, among others--is the show function, defined by the type class Show.

The error you're getting, then, is informing you that you've evaluated an expression of a type that doesn't have an instance of Show defined. Modulo some verbiage, this is all the error message is saying:

No instance for (Show ((t -> t1) -> t -> t1))

The type ((t -> t1) -> t -> t1) is what was inferred for the expression you evaluated. This is a valid type for the Church numeral 1, though the "correct" type for a Church numeral should actually be (a -> a) -> a -> a.

  arising from a use of `print' at <interactive>:1:0-1

It's implicitly using the print function to display the values. Normally this would tell you where in your program the error was found, but in this case it says <interactive>:1:0-1 because the error was caused by an expression in the REPL.

Possible fix:
  add an instance declaration for (Show ((t -> t1) -> t -> t1))

This is just suggesting that you could fix the error by defining the instance it was expecting.


Now, you probably want to actually print your Church numerals, not just know why you can't. Unfortunately, this isn't as simple as adding the instance it asked for: If you write an instance for (a -> a) -> a -> a, Haskell interprets this as an instance for any specific a, whereas the correct interpretation of a Church numeral is a polymorphic function that works on any arbitrary a.

In other words, you want your show function to be something like this:

showChurch n = show $ n (+1) 0

If you really want to, you may implement the Show instance like this:

instance (Show a, Num a) => Show ((a -> a) -> a -> a) where
    show n = show $ n (+1) 0

and add {-#LANGUAGE FlexibleInstances#-} to the first line of the file. Or you may implement something similar to convert them to a regular number

> churchToInt c1
1
> showChurch c1
"1"

etc.

like image 152
C. A. McCann Avatar answered Oct 19 '22 19:10

C. A. McCann