Skip to Content »

Michi’s blog » looksay – today’s Haskell snippet

 looksay – today’s Haskell snippet

  • April 18th, 2007
  • 9:34 am
nextLookSay = foldr (\xs -> ([length xs, head xs]++)) [] . group
lookSay = iterate nextLookSay [1]
 

Conway’s Look-and-say sequence

10 People had this to say...

Gravatar
  • Anonymous
  • April 18th, 2007
  • 16:53

I am once again impressed by how expressive a small amount of Haskell code can be. Nice job!

If you’re interested, an alternative slightly smaller solution would be:

lookSay = iterate (concatMap (\is -> length is : take 1 is) . group) [1]

Gravatar
  • Michi
  • April 18th, 2007
  • 17:12

Neat, I like it. It takes care of a few of the things that bothered me about my own solution – such as the wayward ++ and the seemingly extra imposed square brackets for the data pair.

Gravatar
  • Dan P
  • April 18th, 2007
  • 20:39

I just had to correct that Wikipedia entry. The claim of first publication was, as far as I know, incorrect. Audioactive decay first appeared in the magazine Eureka. Eureka was the magazine of the Cambridge University mathematics society, and I was at around that time an officer of that society. So I was a bit miffed to read that bit of misinformation!

Gravatar
  • Brent
  • April 19th, 2007
  • 18:18

Sorry, what’s the ‘group’ function? It doesn’t seem to be in my standard prelude. Apologies if it’s something you’ve posted before, I just started reading.

Gravatar
  • Michi
  • April 19th, 2007
  • 18:27

Brent: Actually, you’re quite right. ‘group’ isn’t in the Prelude – it’s in Data.List.

Gravatar
  • Brent
  • April 19th, 2007
  • 18:40

Got it, thanks. Nifty. =)

Gravatar

Nice! I was going to suggest refactoring your fold into concat . map, but I see Anonymous has got there first, and with an even better implementation :-)

Naturally, my first question (after “what is this Look and Say sequence of which you speak?”) was “what would the corresponding Perl program look like? Here’s the first script I thought of:

$_ = 1;
for my $i (1..20) {
print “$_\n”;
s/(\d)\1*/length($&).$1/ge
}
Twenty characters shorter, and about as readable to me – though I suspect I may be alone in this opinion! :-)

Gravatar

Thinking a bit more about it, I realise that our two programs will give the same results, but only because of a not-entirely-obvious property of the look-and-say sequence: that it never contains numbers greater than three. Suppose at some point there were a sequence of ten 1s. Your program would turn that into [10,1], which would then become [1,10,1,1] whereas mine would turn it into “101″, which would then become “111011″. The regexp algorithm would treat the 10 as a one followed by a zero, rather than an indivisible number. As I said, this subsequence will never arise in the standard sequence, but it could arise given a different starting number.

Gravatar
  • Michi
  • April 25th, 2007
  • 10:14

Note, though, that if you have something larger than 3 occurring in the seed, then the sequence will decompose into “left of the large” and “right of the large” behaving as expected, and with the large element remaining as an immutable barrier.

If you have repeated barrier elements, they will reduce in one iteration to a single barrier element.

And for things like
155551
you get
114511
21141511
and from this point on, the 4 and 5 act as barriers.

Just realized – the barriers leak 1s to the left.

Gravatar
  • Wuzzy
  • May 18th, 2011
  • 14:26

nice one. Although there is a
import Data.List
missing.

Because its annoying this function does return a list of numbers, it rather returns a list of LISTS of numbers and these numbers are just digits. (You may noticed that if you tried that function in GHCi.) So if you want the real numbers, I’ve written a function which assembles the digit-lists to a number:


digits2number :: [Int] -> Int
digits2number [] = 0
digits2number digits@(d:ds) = d * (10 ^ (length digits - 1)) + digits2number ds

example usage
digits2number [5,3,1,5] = 5315
digits2number [1] = 1
digits2number [] = 0
digits2number [9,9,9,9,9] = 99999

The function returns useless results if one of the elements is a number greater than 9 or smaller than 0.

Then you only need to map this with the return value of lookSay (I guess, didn’t try it [lol]) and you have nice numbers instead of not-so-nice digit-lists. ;-)

Want your say?

* Required fields. Your e-mail address will not be published on this site

You can use the following XHTML tags:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>