Source
[deleted]•

[deleted]

2
polux2001•

That's not the point (see the link): they behave differently.

5
wnoise•

And besides, the second one is more readable.

4
ryani•

Do they? By referential transparency they are the same thing, right? :)

"fix" just optimizes a bit for memory usage, but idealized machines have arbitrary amounts of memory.

fix f = f (fix f)
-- lift subexpressions
fix f = x where
     r = fix f
     x = f r
-- inline fix
fix f = x where
    r = x' where
        r' = fix f
        x' = f r'
    x = f r
-- by referential transparency, r = fix f still
-- So, remove duplicate computation in r'
fix f = x where
    r = x' where
        r' = r
        x' = f r'
    x = f r
-- lift expressions (let of let)
fix f = x where
    r = x'
    r' = r
    x' = f r'
    x = f r
-- inline r' and discard
fix f = x where
    r = x'
    x' = f r
    x = f r
-- remove duplicate computation x'
fix f = x where
    r = x
    x = f r
-- inline r and discard
fix f = x where x = f x
2
doliorules•

By referential transparency, insertion sort and merge sort are the same thing, right?

Denotational semantics aren't the only thing that matters.

2
ryani•

Possibly; there may be some "interesting" Ord instances that cause them to differ.

That said, my post was tongue in cheek. Of course it matters that they perform differently.

1
ryani•

The description of fix in Haskell that was the most intuitive to me was specifying it in terms of defined-ness.

-- Consider
f :: [Int] -> [Int]
f x = 0 : map (+1) x

-- a bottom
undefined :: forall a. a
undefined = error "undefined"

-- now see how it works on various levels of defined arguments
f undefined = 0 : map (+1) undefined
    = 0 : undefined
f (f undefined) = 0 : map (+1) (f undefined)
    = 0 : map (+1) (0 : undefined)
    = 0 : 1 : undefined
f (f (f undefined)) = 0 : map (+1) (f (f undefined))
    = 0 : map (+1) (0 : 1 : undefined) 
    = 0 : 1 : 2 : undefined
fix f = f (f (f (f (f (f (...
    = 0 : 1 : 2 : 3 : 4 : ...

This works because f x, for any x, always agrees with f undefined in any place where the latter is defined. In a way, f undefined is a lower bound on the information returned by f.

2
plesn•

But here you have two notions mixed up : fixed point and infinite lists. This complicates things imho. A fixed point is easier to explain on finite things with recursion. Infinite sequences clicked for me really only when I learned the notions of codata and corecursion ( http://blog.sigfpe.com/2007/07/data-and-codata.html )

2
ryani•

I don't think this has anything to do with infinite lists; here's the gold standard example of fix: fact

factr :: (Int -> Int) -> (Int -> Int)
factr rec 1 = 1
factr rec n = n * rec (n-1)

fact = fix factr

factr undefined 3 = 3 * undefined 2
    = undefined
factr (factr undefined) 3 = 3 * factr undefined 2
    = 3 * (2 * undefined 1)
    = undefined
factr (factr (factr undefined)) 3
    = 3 * factr (factr undefined) 2
    = 3 * (2 * factr undefined 1)
    = 3 * (2 * 1)
    = 6

Similarily to the infinite list example, we push the 'defined'-ness deeper into the computation. fix factr n = factr (factr (factr ...)) n gives you an arbitrary level of defined-ness, just like the previous example gave you an arbitrarily long list.

1
plesn•

Ok, your method of pushing 'defined'-ness makes more sense here for me as the result is clearly defined and terminating.

1
andygillku•

clearly, the second one is better!

1
dmalikov•

Could someone explain how first one actually working?

1
fixedarrowOP•

just apply the definition over and over again...

fix' f
f (fix' f)
f (f (fix' f))
f (f (f (fix' f)))
...
f (f (f (f (f (f (f ...
3
nodefense•

Well nothing could go wrong with that!

1
ehird•

It leaks memory, but apart from that the first definition works just fine in Haskell.

1