2
\$\begingroup\$

Here is a code I experimented with recently:

let br = [0]:[n:(concat $ take n br) | n <- [1..]] in concat br

This code produces the binary rule 0 1 0 2 0 1 0 3 ...

Here is the idea of how it works:

  • create a list starting with [0]

  • each step, concatenate all the current elements in the list, put the next number at the begining and add at the end.

[[0] ...]
[[0], [1, 0] ...]
[[0], [1, 0], [2, 0, 1, 0]...]
[[0], [1, 0], [2, 0, 1, 0], [3, 0, 1, 0, 2, 0, 1, 0] ...]
...

My question now is: is there a shorter/smarter one-liner to get this infinite lazy binary-rule ?

Edit:

I found another way to do the same thing:

let f n = if n==0 then [0] else n:([0..n-1] >>= f) in [0..]>>= f

The extra question would be: wich one of the 2 version is more readable for an haskell programmer, and why ?

\$\endgroup\$
4
  • \$\begingroup\$ Re Edit 2: The python version should be yield 0 \n for b...: yield b+1 \n yield 0 \$\endgroup\$ May 27 at 16:24
  • \$\begingroup\$ Re Edit 2: The haskell version: I confirm that it hangs, and I'm trying to figure out why. This works: import Data.List (intersperse) \n binaryRule = 0 : intersperse 0 ((+1) <$> binaryRule) \$\endgroup\$ May 27 at 16:42
  • \$\begingroup\$ Ok, I figured out the problem, but I think we've pissed off the mods enough with troubleshooting on Code Review, and I want my fake internet points in the right place anyway :) . Open a thread on Stack Overflow and share the link here! \$\endgroup\$ May 27 at 16:47
  • \$\begingroup\$ To be clear chameleon questions - questions where what is being asked changes over time - are not allowed on Code Review. If you'd like advice on working code (which your Edit 2 is not) you can ask a follow-up question. Alternately you could take @ShapeOfMatter up on the offer to ask on Stack Overflow. Please do not undo my rollback or 'the mods' may become pissed off ;) \$\endgroup\$
    – Peilonrayz
    May 27 at 17:16
5
\$\begingroup\$

I'm a little out of practice with haskell, but I'm quite fond of it. I want to address your "extra" question first.

wich one of the 2 version is more readable for an haskell programmer, and why ? [sic]

Haskell programmers aren't a special magic kind of people. They tend to take the benefits of brevity more seriously than folks in love with python, but I think they'll still agree that golfed code is not readable/smarter/better. The basic rule of good (code) writing applies: Write what you mean.

  • create a list starting with [0]
  • each step, concatenate all the current elements in the list, put the next number at the beginning and add at the end.

Neither of your proposed solutions is obviously doing that, although it only takes a minute to see that your first solution is doing that.

Noughtmare's suggestion is based on a different construction of the OEIS sequence, although the OEIS presents this as an invariant, not a construction, so the reader still needs to think the matter through (a little).

Give-or-take efficiency, write code that obviously does what you're saying it does. Unfortunately, the OEIS entry doesn't describe the sequence in terms that translate directly to a lazy infinite list declaration, so you need to provide some documentation of your own.

-- https://oeis.org/A007814
rulerSequence :: [Integer]
rulerSequence = concat halfs
  where seed = [0, 1]
        -- The sequence is built by concatenating with itself
        -- and incrementing the last index. `nextHalf` builds
        -- the right-hand-side of each such concatenation.
        nextHalf priorHalfs = let priors = concat priorHalfs
                              in (init priors) ++ [(last priors) + 1]
        halfs = seed:[nextHalf (take iteration halfs) | iteration <- [1..]]
\$\endgroup\$
2
\$\begingroup\$

I would use an interleave helper:

interleave :: [a] -> [a] -> [a]
interleave (x:xs) ys = x : interleave ys xs

binaryRule :: [Integer]
binaryRule = interleave [0,0..] (map (+ 1) binaryRule)

Or golfed: let(a:b)#c=a:c#b;a=[0,0..]#map(+1)a in a

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.