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
is your tobin actually correcT?
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 ;)
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
I get the right answer
(with your function)
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.)
I like that it jumped from 500 to 2^9001 and neither of them apparently took any longer. :P
ocharles
that's haskell for you :)
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?