Hoodlums Message Board › Could anyone please explain how it works

Could anyone please explain how it works

Rustem S.
user 9259655
London, GB
Post #: 1
Hi Hoodlums,
While learning Haskell I came across a task to generate Golomb_sequence*:

* http://en.wikipedia.o...­

and this solution:

fix ((1:) . (2:) . drop 2 . concat . flip (zipWith replicate) [1..])

Could someone explain how it works?
Or maybe how to rewrite it in a more readable way.

Thank you
Rustem
Duncan M.
user 9754203
London, GB
Post #: 4
Here's an attempt at explaining what's going on... I'm sure this is inaccurate in some specifics, and it's dreadfully wordy, but it was a good exercise for me!! (any comments from people who cringe when they read this would be appreciated! :) )

I'll try to explain it with a bit of equational reasoning... Here goes...

We'll say that a sequence [a_1, a_2, ...] has the Golomb property iff:
i) a_1 = 1
ii) the sequence is nondecreasing
iii) the number n appears exactly a_n times.

A consequence of this is that any such sequence a = [a_1, a_2, ...] consists of some number of 1s, followed by some number of 2s, followed by some number of 3s etc. To see this, just note that any natural number n must appear a_n times in the sequence, and since the sequence is nondecreasing, and a_1 = 1, we know that a_n can't be zero and thus n must appear somewhere. And again, since the sequence is nondecreasing, the natural numbers must appear in order.

This in turn makes it apparent that for any sequence a = [a_1, a_2, ...] with the Golomb property, and sequence b = [b_1, ...] defined by:

b = (concat . flip (zipWith replicate) [1, 2, ...]) a

then b = a --- i.e., 'a' is a fixed point of (concat . flip (zipWith replicate) [1, 2, ...])

This follows because 'b' consists of some number of 1s, followed by some number of 2s etc. (by the definition of 'replicate', 'zipWith', 'flip' and 'concat'); 'b' can thus be completely defined by giving the number of times each natural number appears --- and each number n appears exactly a_n times. However, the same holds true of 'a': it consists of a bunch of 1s followed by 2s followed by 3s etc., and each number n appears a_n times. And so 'a' and 'b' are identical.

So we can see that if the Golomb sequence g = [g_1, ...] exists, it must satisfy:

g = (concat . flip (zipWith replicate) [1,2,...]) g

But that isn't enough information to actually calculate what 'g' is --- there'd be no problem with writing:

> g = (concat . flip (zipWith replicate) [1,2,...]) g

in Haskell. But if you tried to actually extract any elements from g:

> head g
=> never terminates...

However, the last part of the definition of the Golomb sequence must also be satisfied: that is, for each n, g_n must be the smallest possible number such that the Golomb property holds for g. We know that g_1 must be 1, and (since wikipedia told us..) since it's possible that g_2 is a 2, it must be that g_2 is a 2 (if it wasn't possible for g_2 = 2, then g couldn't exist!). This means that 'g' must be a fixed point of:

((1:) . (2:) . drop 2)

that is to say, if you drop the first 2 elements of 'g', then prepend a 2, and then prepend a 1, you get 'g' back again.

This fares a little better as far as calculating g in Haskell goes:

> g = ( (1:) . (2:) . drop 2) g
> head g
=> 1
> (head . tail) g
=> 2

But when we go for the third element of g we run into problems:

> (head . tail . tail) g
=> never terminates...

The trick is to combine the two definitions in such a way that we can calculate just enough of 'g' to bootstrap the rest into existence. We know that we need to know at least the first two elements of 'g' --- and we hope that knowing these two will give enough information for the second relationship to completely nail down 'g':

> g = ((1:) . (2:) . drop 2) g = ((1:) . (2:) . drop 2 . concat . flip (zipWith replicate) [1,2,...]) g

Now we have:
> head g
=> 1
> (head . tail) g
=> 2
> (head . tail . tail) g
=> 2
etc.

To see how this evaluation might work, remember that haskell is lazy --- it only evaluates an expression to the point where it can give the answer that has been requested. In the case of (head g), we have:

head g = head (((1:) . (2:) . drop 2 . concat . flip (zipWith replicate) [1,2,...]) g)
= head (1 : ((2:) . drop 2 . concat . flip (zipWith replicate) [1,2,...]) g) )
= 1

similarly:
(head . tail) g = head (tail (1 : ((2:) . drop 2 . concat . flip (zipWith replicate) [1,2,...]) g )) )
= head (2 : (drop 2 . concat . flip (etc.)))
= 2

and then:
(head . tail . tail) g = head ((drop 2 . concat . flip (zipWith replicate) [1, 2, ...]) g)
= head ((drop 2 . concat . flip (....) [1..]) (((1:) . (2:) . drop 2) g ) (I've cheated a bit here, by just using the first expression for g...)
= head ((drop 2 . concat) (zipWith (1 : 2 : g) [1..]))
= head ((drop 2 . concat) ([1] : [2 : 2] : zipWith replicate g [3..]))
= head (drop 2 (1 : 2 : 2 : concat . zipWith replicate g [3..]))
= head (2 : concat . zipWith replicate g [3..])
= 2

(and it should be fairly obvious that we can continue from here...)

Finally, as for the "fix" operation, this has the definition:

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

writing:

y = fix f

then makes it obvious that y is a fixed point of f:

y = fix f = f (fix f) = f y

When it comes to actually calculating a value for y is that there may be several values satisfying this condition for a given f. Haskell's evaluation strategy determines the fixed point that is actually selected (and ensures that a fixed point always exists, though it may be _|_ --- i.e. a nonterminating computation) --- it selects the "least fixed point". I don't quite understand what this means, but an arm-wavey explanation is that the "least fixed point" is the "least well-defined function that satisfies the fix-point equation". So, for example:

> fix ((1:) . drop 1)
=> [1, _|_]

i.e. the first element must be 1, but the rest of the elements could be anything you wanted... so [1, _|_] is the least well-defined fixed point (or "least upper bound").
Rustem S.
user 9259655
London, GB
Post #: 2
Thank you Duncan!
Very detailed answer!
You saved me from a sleepless night :)
Powered by mvnForum

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy