Haskell


Prelude> \x -> x x

<interactive>:2:9:
    Occurs check: cannot construct the infinite type: t1 = t1 -> t0
    In the first argument of `x', namely `x'
    In the expression: x x
    In the expression: \ x -> x x

Prelude> let y f = \x -> f f x

<interactive>:2:19:
    Occurs check: cannot construct the infinite type:
      t1 = t1 -> t2 -> t0
    In the first argument of `f', namely `f'
    In the expression: f f x
    In the expression: \ x -> f f x


​> (lambda (x) (x x))
#<CLOSURE <anon> (x) (x x)>
​> (define (y f) (lambda (x) (f f x)))
#<unspecified>
​> (define factorial (y (lambda (f n) (if (= n 0) 1 (* n (f f (- n 1)))))))
#<unspecified>
​> (factorial 5)
120

ghci> newtype Rec a = In { out :: Rec a -> a }
ghci> let y f = (\x -> f (out x x)) (In (\x -> f (out x x)))
ghci> let fac = y (\f n -> if n == 0 then 1 else n * f (n-1))
ghci> fac 5
120

>>2
Haskell:


newtype Rec a = In { out :: Rec a -> a }
let y f = (\x -> f (out x x)) (In (\x -> f (out x x)))

Scheme:


(define (y f) (curry f f))


Scheme:


(define (u x) (x x))

Haskell:

???

Although the scheme y combinator isn't quite the same as the haskell y combinator there. I'm going to see if you can explain why. this tests if you understand the code, as opposed to just copying it from stackoverflow

>>3
Everyone knows y is cannot be directly expressed with Hindley-Milner types. You are not working in an untyped lambda calculus. 

Use fix for you fixpoints:


fix :: (a -> a) -> a
fix f = let x = f x in x

Expansion:


let x = f x =>
let x = f (f x) =>
let x = f (f (f x)) ..

>>3
!!!

>infinite type
Shalom!

Symta doesn't need jewish y-combinator.

Idiots can't even into type theory? No wonder lishp is so obsolete.

>>7
EBIG GWODE /G/RO XDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD LEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEL

>>9
People on /g/ never speak like this.

Thread reported and dubs checked.

>>1
Prelude> \x -> x x
Functions are not an instance of show.  Typing in a lambda expression without evaluating it does not work.

Also, check your type signature.
(x -> (x -> ( x -> (x -> (x ->

>>12
More like check your statically typed privilege.

Hymie-Nigger types

>>5
That expression of fix, however neat it may be, wont terminate when I try to use it. What exactly does x = f x do in haskell?

>>8
These types are finite and recursive. You just can't write them out in the simplistic way, like how you can't pin down a circle on a flat strip of tape. Haskell can't do recursive types. And I wish it could. The real y combinator would be:


let y f = f (y f)

Scheme has the flexibility of being untyped, but this isn't as short in scheme because of strict evaluation and no implicit currying.


(define (y f) (lambda args (apply f (cons (y f) args))))

>>12
And the not an instance of show ain't the error I'm gettin, which is why I don't try any further.

Correcting, Haskell can't do recursive type inference.

RECURSIVELY TYPE INFER MY ANUS!

Wait a minute what the fuck am I saying. y f = f (y f) doesn't give a recursive type and it works perfectly fine in haskell.


Prelude> let y f = f (y f)
Prelude> let fac = y (\f n -> if n == 0 then 1 else n * f(n-1))
Prelude> fac 5
120


y :: (a -> a) -> a
y f = f (y f)

you need to correct me more /prog/. So all scheme has over haskell is the u combinator, which isn't that great, but it still has its uses. Sometimes you need a reference to a function without having it y combinated.

>>15
It works fine by me:

fix (const 1) => 1

let b = fix (\f n -> if n < 1 then 1 else f (n - 1) + f (n - 2))

:t b
b :: Integer -> Integer
b 9
144

What exactly does x = f x do in haskell?

The let is a letrec (if I translate it to scheme), so it should expand to this:

let x = f x in x =>
let x = f (f x) in x =>
let x = f (f (f x)) in x => ..

if I put const 1 in there as f, we get:

let x = const 1 x in x =>
let x = const 1 (const 1 x) in x =>
The compiler knows the second argument expands, but const isn't strict in its second argument, thus it won't expand the expression further.
let x = const 1 <thunk> in x
evaluating gives us:
let x = (\a _ -> a) 1 thunk in x
let x = 1 in x =>
1

>>18
That's a nice trick! Though it does appear a bit of a hack. It is more `standard' in Common Lisp with the LABELS macro.