Wondrous Functional Languages

My colleague Matt wrote about a recent Ruby Quiz which emphasised short, elegant solutions. He was particularly impressed with a solution which used a property of Ruby hashes to generate a wondrous number sequence for any given integer in a single line of code.

That got me thinking about the solution in Scheme, a language I find very appealing, and Haskell, which I had started picking up a few months ago but had to abandon due to lack of time. Even so I managed to remember enough to get this basic solution within a few minutes:

wondrous :: Int -> [Int]
wondrous 1 = [1]
wondrous x
	| even x = x : wondrous (x `div` 2)
	| otherwise = x : wondrous (3*x+1)

Here is the most obvious implementation in Scheme:

(define wondrous
  (lambda (x)
    (cond
      ((= x 1) ‘(1))
      ((= (modulo x 2) 0) (cons x (wondrous (quotient x 2))))
      (else (cons x (wondrous (+ (* 3 x) 1))))
    )
  )
)

As you can see both of these functional languages are really suited to expressing such algorithms, particularly Haskell with its excellent pattern matching expressions. I have no doubts that there are far more elegant solutions in both languages; I’ll post them if I get suitably inspired.

Join the Conversation

1 Comment

  1. Ooh! A fellow haskell-dude!

    Nitpick:
    Specifying the type manually can have bad effects;
    wondrous :: Int -> [Int]
    but if you asked GHC what type it thought it should have, you’d get
    wondrous :: Integral a => a -> [a]
    which has the nice effect of letting you use BigInts too. 🙂

    (Although maybe you just wanted to keep it simple and more easily understandable to non-Haskellers.. I don’t know)

Leave a comment

Your email address will not be published. Required fields are marked *