#bookbrainz-devel

ocharles, is the ++ thing what you meant by converting it to a left fold algorithm?

oh, sorry I forgot to reply

No worries.

and no, not quite

Essentially you replace the whole logic of recursion with a call to foldl

Ahh.

Oh, right.

left folding means you are tail recursion and can run in constant space

but more because appreciating that the general process of recursion can be abstracted into a fold is quite a good exercise :)

There are also catamorphishms - a catamorphism is to trees, what folds are to lists

if I understand correctly :)

I suppose the difficulty I have thinking of this as a fold is this: a fold operates on a list, right? So how do I take a scalar and fold it?

right, but your integer can be broken down to into a list of magnitudes (right number) ?

s/(right number) ?/(right term?)/

Hmm.

ie, 1001 = [1, 0, 0, 1]

that's one representation, not the only one

Right. I'm just not seeing how to use a fold on a scalar, say 19, to get those out since it's only operating on one element rather than applying something to a series of elements.

right

maybe this isn't the best place to learn about folds :)

I've read about folds, and have a general idea of how to use them. Just not sure how they could apply here.

I was actually thinking of implementing a Gray code successor function based on a fold.

Since the binary representation already reads low bit to high, the Gray code successor would be relatively simple.

is your tobin actually correcT?

In the sense of does it give the right output?

yea, mine fold version gives something different for "tobin 500" :)

tobin 4 looks wrong

reverse $ tobin 4

mm

For computational efficiency, the list is built with the low bit leftmost.

ok, got something equivilent

foldl (\bin x -> x `mod` 2 : bin) [] $ takeWhile (> 0) $ iterate (`div` 2) 500

now we can use Criterion (see hackage) to benchmark these

we could also use QuickCheck to assert that they are the same

I'll have to go over yours when I'm less tired.

:)

For today, I'm pretty pleased that I managed to write an arbitrary precision decimal to binary conversion in three lines of Haskell.

yea, not gonna knock that!

just continuing to push you out of your comfort zone ;)

Oh, no, I definitely appreciate that.

Getting me out of that is a Good Thing.

tobin = map (`mod` 2) . takeWhile (> 0) . iterate (`div` 2)

is another idea

that's a fairly natural extension of the idea that map is a fold with the list construction operator

Heh, I just threw some huge integer value into tobin and did a quick (not full) check on WolframAlpha. Looks correct for the first and last ten digits of 142. :P

haha

An Integer or an Int?

I just used Integral.

right, but that's both Int and Integer

Int has bounds

Oh. I misunderstood the question.

Integer.

a

Got WolframAlpha to give me the value of 2^1000 and chucked it in. A single one and lots of zeros.

Pretty sure that's an Integer value.

I get the right answer

(with your function)

Sweet.

what did you get?

For 2^1000?

yea

Leftmost one (after reverse) and too many zeros for me to want to count.

but that's correct, no?

Yes.

oh, I thought you were saying it was wrong

I'm just going to assume that it's a thousand zeros.

Oh, nope.

length it

1001

that sounds correct

Well geez, it sure looks like more than nine values! :P

It is.

(For example, 2^2 = 4 is 100, and so has 2 trailing zeros.)

or more 2^0 is [1] :)

Yeah, but 2^2 is a nicer example. :)

Okay. Time for me to sleep 14400.

hold up

lets profile first :P

only take a moment!

Okay. I'll brush my teeth while we wait.

comment added with 2 ^ 9001

I like that it jumped from 500 to 2^9001 and neither of them apparently took any longer. :P

that's haskell for you :)

Also like that yours is indeed about five times as fast, shaving off a full microsecond. :P

haha

well, if it's a hotspot, that's important :)

Oh, no doubt. I'm just very amused by the scale of it all.

yea, heh

G'night, and thanks for being as ridiculously excited about Haskell implementations of binary conversion as I am.

haha

happy binary dreams

So does iterate just create an infinite list with the given function on the given input by running it on the input, then running it on the last element of the list repeatedly?