OCaml can do this: $ ocaml -rectypes Objective Caml version 3.11.1 # let fix f = (fun x -> f(x x)) (fun x y -> f(x x) y);; val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> # fix (fun f -> function 0 -> 1 | n -> n*f(n-1)) 10;; - : int = 3628800 Haskell 98 doesn't seem to be able to type check that definition of the y-combinator directly. Is there a Haskell extension that would let it handle this? -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e
http://lmgtfy.com/?q=y+combinator+haskell Cheers, Edgar On Wed, 24/Feb/2010 at 20:41 +0000, Jon Harrop wrote:
OCaml can do this:
$ ocaml -rectypes Objective Caml version 3.11.1
# let fix f = (fun x -> f(x x)) (fun x y -> f(x x) y);; val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
# fix (fun f -> function 0 -> 1 | n -> n*f(n-1)) 10;; - : int = 3628800
Haskell 98 doesn't seem to be able to type check that definition of the y-combinator directly. Is there a Haskell extension that would let it handle this?
-- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
Excerpts from Jon Harrop's message of Wed Feb 24 15:41:01 -0500 2010:
OCaml can do this:
$ ocaml -rectypes Objective Caml version 3.11.1
# let fix f = (fun x -> f(x x)) (fun x y -> f(x x) y);; val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
# fix (fun f -> function 0 -> 1 | n -> n*f(n-1)) 10;; - : int = 3628800
http://haskell.org/hoogle/3/?q=fix Cheers, Edward
On Wednesday 24 February 2010 20:53:14 Edward Z. Yang wrote:
That leads to the following source: http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Function.htm... but it uses a workaround rather than extending the type system. I'm looking for an equivalent of OCaml's -rectypes that enables recursive types in Haskell (e.g. in ghci)? -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e
On Wed, Feb 24, 2010 at 11:53:50PM +0000, Jon Harrop wrote:
On Wednesday 24 February 2010 20:53:14 Edward Z. Yang wrote:
That leads to the following source:
http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Function.htm...
but it uses a workaround rather than extending the type system. I'm looking for an equivalent of OCaml's -rectypes that enables recursive types in Haskell (e.g. in ghci)?
Haskell has recursive types, but they are iso-recursive rather than equi-recursive; the recursion must always be guarded by a data constructor. I am not sure what you mean by saying that Data.Function contains a "workaround". What exactly are you trying to do? -Brent
On Thursday 25 February 2010 00:31:59 Brent Yorgey wrote:
On Wed, Feb 24, 2010 at 11:53:50PM +0000, Jon Harrop wrote:
On Wednesday 24 February 2010 20:53:14 Edward Z. Yang wrote:
That leads to the following source:
http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Function. html
but it uses a workaround rather than extending the type system. I'm looking for an equivalent of OCaml's -rectypes that enables recursive types in Haskell (e.g. in ghci)?
Haskell has recursive types, but they are iso-recursive rather than equi-recursive; the recursion must always be guarded by a data constructor. I am not sure what you mean by saying that Data.Function contains a "workaround".
Guarding the recursion with a constructor is the workaround I was referring to, like this: # let fix f = (fun (`X x) -> f(x (`X x))) (`X(fun (`X x) y -> f(x (`X x)) y));; val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
What exactly are you trying to do?
I'm wondering if it is possible to get this to type in Haskell without altering the code, i.e. by enabling recursive types in the compiler as I did with OCaml using -rectypes. -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e
On Thu, Feb 25, 2010 at 03:32:25AM +0000, Jon Harrop wrote:
On Thursday 25 February 2010 00:31:59 Brent Yorgey wrote:
On Wed, Feb 24, 2010 at 11:53:50PM +0000, Jon Harrop wrote:
Haskell has recursive types, but they are iso-recursive rather than equi-recursive; the recursion must always be guarded by a data constructor. I am not sure what you mean by saying that Data.Function contains a "workaround".
Guarding the recursion with a constructor is the workaround I was referring to, like this:
# let fix f = (fun (`X x) -> f(x (`X x))) (`X(fun (`X x) y -> f(x (`X x)) y));; val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
What exactly are you trying to do?
I'm wondering if it is possible to get this to type in Haskell without altering the code, i.e. by enabling recursive types in the compiler as I did with OCaml using -rectypes.
No, it isn't. There's no equivalent of -rectypes in any Haskell compiler I'm aware of. -Brent
On Thu, 25 Feb 2010 03:32:25 +0000, Jon Harrop
On Thursday 25 February 2010 00:31:59 Brent Yorgey wrote:
On Wed, Feb 24, 2010 at 11:53:50PM +0000, Jon Harrop wrote:
On Wednesday 24 February 2010 20:53:14 Edward Z. Yang wrote:
That leads to the following source:
http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Function. html
but it uses a workaround rather than extending the type system. I'm looking for an equivalent of OCaml's -rectypes that enables recursive types in Haskell (e.g. in ghci)?
Haskell has recursive types, but they are iso-recursive rather than equi-recursive; the recursion must always be guarded by a data constructor. I am not sure what you mean by saying that Data.Function contains a "workaround".
Guarding the recursion with a constructor is the workaround I was referring to, like this:
# let fix f = (fun (`X x) -> f(x (`X x))) (`X(fun (`X x) y -> f(x (`X x)) y));; val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
If the reason for avoiding a data constructor is performances, then Haskell "newtype"s will help. -- Nicolas Pouillard http://nicolaspouillard.fr
participants (5)
-
Brent Yorgey -
edgar＠ymonad.com -
Edward Z. Yang -
Jon Harrop -
Nicolas Pouillard