Posts

Showing posts from May 19, 2013

Baby's First Type

If we're going to use van Laarhoven's trees, we have to create a type and define a meet operation on it that satisfies the semilattice properties, so it can take its rightful place in the Semilattice type class. Then we can use fromList to create a tree and search it.

(By the way, we've gone a long way with just a few built-in types. Initially we were using floating point, but that was in fact a bug because of the size of the integers we have to deal with. That leaves Int (fixed-size integer), Integer (arbitrary-precision integer aka "bignum"), and lists. Aside from Lisp, how many of the languages atop the TIOBE Index could one do this in purely with built-in types?)

So, how do you create a type in Haskell?

In our earlier code fragment, we supposed we could use a (Int, Integer)to hold a d-digit Y value and its ordinal position in the list of all d-digit Y values (though not in that order!). Perhaps we can use type, which just lets you refer to a type by a name of…

Feeling like David Hilbert?

Remember the big brouhaha back in the late 19th and early 20th century about the foundations of mathematics? There was one radical school of thought, the Intuitionists, who insisted on constructive proofs. They held the method of "indirect proof", i.e. suppose what you wish to prove is false, and then show that a contradiction results, to be invalid, and disagreed with the "law of the excluded middle", that any given proposition is either true or false.

This was pretty controversial stuff, and David Hilbert wrote the following famous line about it: taking the principle of the excluded middle from the mathematician is the same as denying the telescope to the astronomer, or the boxer the use of his fists.

As a programmer brought up on imperative languages, I have to wonder whether those of similar training feel about pure applicative languages the way Hilbert did about intuitionism.

A must-read from Jeremy Bowers

"Why I'm Interested in Haskell"--not the writing of a fanboy, but of someone who I think fairly assessed the state of the programming language world at the time of writing (mid-April 2011).

A should-read from Evan Laforge

"What Haskell Doesn't Have"...thank goodness.

Advice on Haskell from that great philosopher, Bo Diddley

Don't let your instance write a check that your type can't cash.

Haskell's type checking is a glorious thing and saves one--let's be honest, saves me--from lots of stupid mistakes. However, there's one thing that it can't do for you. When you say a type is an instance of a type class, it has to trust that the operations you define on the type to gain admission to the type class behave the way they're supposed to. So be careful.

By golly...

...I think van Laarhoven's data structure is the way to go.

You'll recall that his "Search trees without sorting" stores the upper bounds of trees to speed up queries of the form "what's the first item with a key >= some value?" If we label the sorted d-digit Ys with their ordinal position:

addOrd :: [a] -> [(Int, a)]

addOrd xs = addOrd' xs 1
    where  addOrd' []   _ = []
           addOrd' x:xs n = (n, x) : addOrd' xs (n + 1)

(Is there a slick way to do that with a fold?  I'll have to look for one. UPDATE: no, but there's still a better way; see below)

then we put the results into one of van Laarhoven's semilattice trees and have

ysInRange m n d
   | nval == n = nPos - mPos + 1
   | otherwise = nPos - mPos
   where (mPos, mVal) = -- first entry w/ d-digit Y >= m
         (nPos, nVal) = -- first entry w/ d-digit Y >= n

OK, not quite, since n may be greater than the last d-digit Y, so we'd have to take care of that cas…

Great Leap Forward

So, we made the change. Note that we are in fact generating the lists for the combinations!

{-
  Here's our new approach: rather than generate the upper half separately and
  then have to reverse it a digit at a time, we generate both halves at the
  same time, when we have information we need to do so.

  So, out with backwards and {odd,even}DigitsPal, and twoTwos goes back to its
  simple self.
-}

twoTwos :: Int -> [Integer]

twoTwos n
    | n == 1    = []
    | even n    = [twoTwosNoOnes]
    | otherwise = [twoTwosNoOnes, twoTwosNoOnes + 10 ^ (n `div` 2)]               
    where twoTwosNoOnes = 2 * tenToThe (n - 1) + 2

oneTwos :: Int -> [Integer]

oneTwos n
    | n == 1     = [2]
    | even n     = []
    | otherwise  = [p + 2 * tenToThe halfN
                      | p <- justOnes n (min 1 (halfN - 1))]
    where halfN = n `div` 2

noTwos :: Int -> [Integer]

noTwos n
    | n == 1     = [1,3]
    | even n     = base
    | otherwise  = concat [[p, p + tenToThe halfN] | p <- base]
    where ha…