#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
        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 ;)
      • 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
        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.)
      • ocharles
        or more 2^0 is [1] :)
      • 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
        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?
      • Dremora joined the channel