Dabbling with Haskell

Recently I've been working on a hard programming problem. It's one of ITA's hiring puzzles.

Palindromic Pangram A palindrome is a sequence of words like "lid off a daffodil" or "shallot ayatollahs" that uses the same letters reading backwards as forwards. The words need not form a meaningful or grammatical sentence.

A palindromic pangram is a multi-word palindrome that includes all 26 letters of the alphabet. Find the shortest sequence of words that is both a pangram and a palindrome.

I've been using Scheme to solve it, but since I've been reading a lot of Haskell books lately, I wanted to try to solve the problem with it. The results so far have been interesting. Rather than trying to create an efficient solution, I just wanted to see if I could create an "Executable Specification" of the solution.

What I have found most interesting is that lazy evaluation has allowed a very concise solution. Since the lists are lazily evaluated, large lists don't use up all 2 gigs of RAM on my home machine. But given the size of the input dictionary, a solution this naive will not terminate in a reasonable amount of time (if you define my lifetime to be a reasonable amount of time).

Even though I will still use Scheme for this problem, Haskell has given me a bit of a new perspective.

-- The MIT License

-- Copyright (c) 2008 William Emerison Six

-- Permission is hereby granted, free of charge, to any person obtaining a copy
-- of this software and associated documentation files (the "Software"), to deal
-- in the Software without restriction, including without limitation the rights
-- to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-- copies of the Software, and to permit persons to whom the Software is
-- furnished to do so, subject to the following conditions:

-- The above copyright notice and this permission notice shall be included in
-- all copies or substantial portions of the Software.

-- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-- FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-- AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-- LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
-- THE SOFTWARE.

module Main where
import List (find,intersect)
import System.IO

alphabet :: String
alphabet = "abcdefghijklmnopqrstuvwxyz"

flatmap :: (a -> [b]) -> [a] -> [b]
flatmap p s = foldr (++) [] $ map p s

flatten :: [[a]] -> [a]
flatten = flatmap id

permutations :: (Eq e, Integral i) => [e] -> i -> [[e]]
permutations [] _    =  [[]]
permutations _  0    =  [[]]
permutations list k  =  flatmap perms list
    where perms h = map (\t -> h:t) $ permutations (filter (\x -> h /= x) list) $ k - 1
          
pangram :: [String] -> Bool
pangram sentence = alphabet == intersect alphabet (flatten sentence)

palindrome :: [String] -> Bool
palindrome sentence = s == reverse s where s = flatten sentence

pangramicPalindrome :: [String] -> Bool
pangramicPalindrome sentence = and [pangram sentence, palindrome sentence]
                           
findShortestPangramicPalindrome :: [String] -> [String]
findShortestPangramicPalindrome wordSet = head [s |
                                               k <- [1..],                                                                                                 
                                               s <- permutations wordSet k,                             
                                               pangramicPalindrome s]
 wordSet :: IO [String]
 wordSet = do
       f <- readFile "WORD.LST"
       return $ lines f  
 main :: IO () 
 main = do
       ws <- wordSet
       print $ findShortestPangramicPalindrome ws