# #bookbrainz-devel

/
• reosarevok joined the channel
• Leftmost joined the channel
• ianmcorvidae|alt joined the channel
• ianmcorvidae joined the channel
• ianmcorvidae joined the channel
• djce joined the channel
• reosarevok joined the channel
• Leftmost
ocharles, is the ++ thing what you meant by converting it to a left fold algorithm?
• ocharles
oh, sorry I forgot to reply
• Leftmost
No worries.
• ocharles
and no, not quite
• Essentially you replace the whole logic of recursion with a call to foldl
• Leftmost
Ahh.
• Oh, right.
• ocharles
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 :)
• Leftmost
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?
• ocharles
right, but your integer can be broken down to into a list of magnitudes (right number) ?
• s/(right number) ?/(right term?)/
• Leftmost
Hmm.
• ocharles
ie, 1001 = [1, 0, 0, 1]
• that's one representation, not the only one
• Leftmost
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.
• ocharles
right
• maybe this isn't the best place to learn about folds :)
• Leftmost
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.
• ocharles
• Leftmost
In the sense of does it give the right output?
• ocharles
yea, mine fold version gives something different for "tobin 500" :)
• tobin 4 looks wrong
• Leftmost
reverse \$ tobin 4
• ocharles
mm
• Leftmost
For computational efficiency, the list is built with the low bit leftmost.
• ocharles
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
• Leftmost
I'll have to go over yours when I'm less tired.
• ocharles
:)
• Leftmost
For today, I'm pretty pleased that I managed to write an arbitrary precision decimal to binary conversion in three lines of Haskell.
• ocharles
yea, not gonna knock that!
• just continuing to push you out of your comfort zone ;)
• Leftmost
Oh, no, I definitely appreciate that.
• Getting me out of that is a Good Thing.
• ocharles
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
• Leftmost
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
• ocharles
haha
• An Integer or an Int?
• Leftmost
I just used Integral.
• ocharles
right, but that's both Int and Integer
• Int has bounds
• Leftmost
Oh. I misunderstood the question.
• Integer.
• ocharles
a
• Leftmost
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.
• ocharles
• Leftmost
Sweet.
• ocharles
what did you get?
• Leftmost
For 2^1000?
• ocharles
yea
• Leftmost
Leftmost one (after reverse) and too many zeros for me to want to count.
• ocharles
but that's correct, no?
• Leftmost
Yes.
• ocharles
oh, I thought you were saying it was wrong
• Leftmost
I'm just going to assume that it's a thousand zeros.
• ocharles understands now :)
• Oh, nope.
• ocharles
length it
• Leftmost
1001
• ocharles
that sounds correct
• Leftmost
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.)
• ocharles
or more 2^0 is  :)
• Leftmost
Yeah, but 2^2 is a nicer example. :)
• Okay. Time for me to sleep 14400.
• ocharles
hold up
• lets profile first :P
• only take a moment!
• Leftmost
Okay. I'll brush my teeth while we wait.
• ocharles
• comment added with 2 ^ 9001
• Leftmost
I like that it jumped from 500 to 2^9001 and neither of them apparently took any longer. :P
• ocharles
• Leftmost
Also like that yours is indeed about five times as fast, shaving off a full microsecond. :P
• ocharles
haha
• well, if it's a hotspot, that's important :)
• Leftmost
Oh, no doubt. I'm just very amused by the scale of it all.
• ocharles
yea, heh
• Leftmost
G'night, and thanks for being as ridiculously excited about Haskell implementations of binary conversion as I am.
• ocharles
haha
• happy binary dreams
• kepstin-laptop joined the channel
• kepstin-laptop joined the channel
• kepstin-laptop joined the channel
• kepstin-laptop joined the channel
• kepstin-laptop joined the channel
• kepstin-laptop joined the channel
• kepstin-laptop joined the channel
• djce joined the channel
• Leftmost joined the channel
• Leftmost
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?
• Dremora joined the channel