10:51 am, 30 Aug 06
solving knowledge puzzles
Someone on a mailing list at work forwarded one of those logic puzzles that involve information being revealed by not knowing. Briefly: two numbers in [2,100] are chosen; A is told their product, B is told their sum; A says they don't know the numbers, B says they knew that fact and they also don't know the numbers; and with that knowledge A now knows the numbers.
It turns out that McCarthy wrote a paper: Formalization of two Puzzles Involving Knowledge on solving these puzzles in code.
And based on that, here's a Haskell solution to the problem that is quite nice -- ~20 lines of rather straightforward code. (On the other hand, I imagine that this is the sort of thing a logic programming language is more appropriate for.)
It turns out that McCarthy wrote a paper: Formalization of two Puzzles Involving Knowledge on solving these puzzles in code.
And based on that, here's a Haskell solution to the problem that is quite nice -- ~20 lines of rather straightforward code. (On the other hand, I imagine that this is the sort of thing a logic programming language is more appropriate for.)
If you're referring to the solution, I think it basically brute-force tests all possible combinations of [2,100]x[2,100]. So there's iteration in testing those pairs, and it's done in the list comprehension in result.
In Haskell they look like
[x | y < z]"all" is just true whenever a predicate is true for all the elements in a list. Here's the best way to look at the docs:
http://www.haskell.org/hoogle/?q=all
(it's the first result, Prelude.all)
all ($ (a,b)) [fact1,fact2,fact3,fact4,fact5]could be sorta expressed in C as:
fact1(a, b) && fact2(a,b) && fact3(a,b) && fact4(a,b) && fact5(a,b)examples
Are all of [1,2,3,4] greater than zero?all (> 0) [1,2,3,4]Are all of the characters in the string "foobar" lowercase?
all Char.isLower "foobar"Suppose you prompt a user for some numbers 1 through 23. Multiple answers are okay. (One place where this can happen for example is asking for the closest mirrors to them.) You want to validate every number the user gave is inside the valid range. A manually recursive function to do this might be:
The first thing a functional programmer would note is that this hardcoded the condition -- it's entirely likely you'd want a function like this that didn't just work for the 1 .. 23 range, or even for integer ranges at all! So lets factor that out.
(If you aren't familiar with it, "a" is a polymorphic type notation. And the parentheses around (a -> Bool) mean that the first argument to allValid is a function taking some type and returning Bool. The parameter could have been named "validationFunction" instead of "f", but Haskellers for some reason like to abbreviate.) This is more like it, but this recursion itself here is already redoing something you've done a million times. After all, what we're doing is taking a list of inputs:and transforming them to whether they each pass the validation or not (this is called a map): and then taking that list and reducing it by conjunction^W^W^W^Wreplacing the commas with &&:This is called a fold, and here's the resulting function:
This is quite unweildy, but mostly because of the transformation and because we put our particular validation function inline in the function. Refactored, that would be:Now this is elegant enough! But since it's still pretty common, it's in the Prelude, so you can just doand get your result! If in ghci (or Hoogle) you look at the type signature of
all, you get(a -> Bool) -> [a] -> Bool-- which is what we expected.If automatic prooffinding programs become popular, wow I hope they emit observations like this one.
http://nibot-lab.livejournal.com/40832.html