Essentially you replace the whole logic of recursion with a call to foldl
2012-02-01 03218, 2012
Leftmost
Ahh.
2012-02-01 03222, 2012
Leftmost
Oh, right.
2012-02-01 03226, 2012
ocharles
left folding means you are tail recursion and can run in constant space
2012-02-01 03205, 2012
ocharles
but more because appreciating that the general process of recursion can be abstracted into a fold is quite a good exercise :)
2012-02-01 03234, 2012
ocharles
There are also catamorphishms - a catamorphism is to trees, what folds are to lists
2012-02-01 03239, 2012
ocharles
if I understand correctly :)
2012-02-01 03215, 2012
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?
2012-02-01 03258, 2012
ocharles
right, but your integer can be broken down to into a list of magnitudes (right number) ?
2012-02-01 03210, 2012
ocharles
s/(right number) ?/(right term?)/
2012-02-01 03222, 2012
Leftmost
Hmm.
2012-02-01 03225, 2012
ocharles
ie, 1001 = [1, 0, 0, 1]
2012-02-01 03252, 2012
ocharles
that's one representation, not the only one
2012-02-01 03249, 2012
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.
2012-02-01 03210, 2012
ocharles
right
2012-02-01 03218, 2012
ocharles
maybe this isn't the best place to learn about folds :)
2012-02-01 03246, 2012
Leftmost
I've read about folds, and have a general idea of how to use them. Just not sure how they could apply here.
2012-02-01 03235, 2012
Leftmost
I was actually thinking of implementing a Gray code successor function based on a fold.
2012-02-01 03216, 2012
Leftmost
Since the binary representation already reads low bit to high, the Gray code successor would be relatively simple.
2012-02-01 03251, 2012
ocharles
is your tobin actually correcT?
2012-02-01 03237, 2012
Leftmost
In the sense of does it give the right output?
2012-02-01 03249, 2012
ocharles
yea, mine fold version gives something different for "tobin 500" :)
2012-02-01 03208, 2012
ocharles
tobin 4 looks wrong
2012-02-01 03231, 2012
Leftmost
reverse $ tobin 4
2012-02-01 03249, 2012
ocharles
mm
2012-02-01 03259, 2012
Leftmost
For computational efficiency, the list is built with the low bit leftmost.
2012-02-01 03256, 2012
ocharles
ok, got something equivilent
2012-02-01 03213, 2012
ocharles
foldl (\bin x -> x `mod` 2 : bin) [] $ takeWhile (> 0) $ iterate (`div` 2) 500
2012-02-01 03253, 2012
ocharles
now we can use Criterion (see hackage) to benchmark these
2012-02-01 03208, 2012
ocharles
we could also use QuickCheck to assert that they are the same
2012-02-01 03221, 2012
Leftmost
I'll have to go over yours when I'm less tired.
2012-02-01 03207, 2012
ocharles
:)
2012-02-01 03210, 2012
Leftmost
For today, I'm pretty pleased that I managed to write an arbitrary precision decimal to binary conversion in three lines of Haskell.
2012-02-01 03216, 2012
ocharles
yea, not gonna knock that!
2012-02-01 03228, 2012
ocharles
just continuing to push you out of your comfort zone ;)
that's a fairly natural extension of the idea that map is a fold with the list construction operator
2012-02-01 03232, 2012
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
2012-02-01 03230, 2012
ocharles
haha
2012-02-01 03246, 2012
ocharles
An Integer or an Int?
2012-02-01 03213, 2012
Leftmost
I just used Integral.
2012-02-01 03232, 2012
ocharles
right, but that's both Int and Integer
2012-02-01 03239, 2012
ocharles
Int has bounds
2012-02-01 03254, 2012
Leftmost
Oh. I misunderstood the question.
2012-02-01 03259, 2012
Leftmost
Integer.
2012-02-01 03215, 2012
ocharles
a
2012-02-01 03242, 2012
Leftmost
Got WolframAlpha to give me the value of 2^1000 and chucked it in. A single one and lots of zeros.
2012-02-01 03215, 2012
Leftmost
Pretty sure that's an Integer value.
2012-02-01 03227, 2012
ocharles
I get the right answer
2012-02-01 03238, 2012
ocharles
(with your function)
2012-02-01 03247, 2012
Leftmost
Sweet.
2012-02-01 03254, 2012
ocharles
what did you get?
2012-02-01 03200, 2012
Leftmost
For 2^1000?
2012-02-01 03212, 2012
ocharles
yea
2012-02-01 03215, 2012
Leftmost
Leftmost one (after reverse) and too many zeros for me to want to count.
2012-02-01 03225, 2012
ocharles
but that's correct, no?
2012-02-01 03227, 2012
Leftmost
Yes.
2012-02-01 03240, 2012
ocharles
oh, I thought you were saying it was wrong
2012-02-01 03252, 2012
Leftmost
I'm just going to assume that it's a thousand zeros.
2012-02-01 03254, 2012
ocharles understands now :)
2012-02-01 03255, 2012
Leftmost
Oh, nope.
2012-02-01 03256, 2012
ocharles
length it
2012-02-01 03216, 2012
Leftmost
1001
2012-02-01 03232, 2012
ocharles
that sounds correct
2012-02-01 03236, 2012
Leftmost
Well geez, it sure looks like more than nine values! :P
2012-02-01 03237, 2012
Leftmost
It is.
2012-02-01 03258, 2012
Leftmost
(For example, 2^2 = 4 is 100, and so has 2 trailing zeros.)
I like that it jumped from 500 to 2^9001 and neither of them apparently took any longer. :P
2012-02-01 03258, 2012
ocharles
that's haskell for you :)
2012-02-01 03239, 2012
Leftmost
Also like that yours is indeed about five times as fast, shaving off a full microsecond. :P
2012-02-01 03243, 2012
ocharles
haha
2012-02-01 03255, 2012
ocharles
well, if it's a hotspot, that's important :)
2012-02-01 03223, 2012
Leftmost
Oh, no doubt. I'm just very amused by the scale of it all.
2012-02-01 03231, 2012
ocharles
yea, heh
2012-02-01 03216, 2012
Leftmost
G'night, and thanks for being as ridiculously excited about Haskell implementations of binary conversion as I am.
2012-02-01 03225, 2012
ocharles
haha
2012-02-01 03229, 2012
ocharles
happy binary dreams
2012-02-01 03228, 2012
kepstin-laptop joined the channel
2012-02-01 03224, 2012
kepstin-laptop joined the channel
2012-02-01 03241, 2012
kepstin-laptop joined the channel
2012-02-01 03249, 2012
kepstin-laptop joined the channel
2012-02-01 03251, 2012
kepstin-laptop joined the channel
2012-02-01 03255, 2012
kepstin-laptop joined the channel
2012-02-01 03251, 2012
kepstin-laptop joined the channel
2012-02-01 03204, 2012
djce joined the channel
2012-02-01 03226, 2012
Leftmost joined the channel
2012-02-01 03253, 2012
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?
