Rotonyms in Haskell
- Magnus Therning
I have to say rotonyms seem kind of pointless, but since there is a post with a Python solution I thought I’d make an attempt at a solution in Haskell. Of course I didn’t manage on my own, I received some much needed help from Cale and dmwit on #haskell
.
First some rotation functions, as far as I know there’s no built-in rot13 encoding in Haskell:
rot13Char c = chr ( (ord c - ord 'a' + 13) `mod` (ord 'z' - ord 'a' + 1) + ord 'a')
rot13 = map rot13Char
In order to ease working with rotonyms I introduced a type to represent one. This turned out to pay off later on.
data Rotonym = R String
It would be easy to let the compiler derive Show
, but I wanted to mimick the output produced by Will’s solution in Python:
instance Show Rotonym where
show (R w) =
let r = rot13 w
in (min w r) ++ "\t" ++ (max w r)
Now I’m ready for the meat of the matter, reading the word list, pick out the rotonyms and finally print them. Following Will’s cue I represent the word list as a set of strings (importing Data.Set
as S
), this also eliminates duplicates.
main = do
words <- liftM lines $ readFile "WORD.LST"
let wordset = S.fromList words
isRotonym w = S.member (rot13 w) wordset
rots = S.fromList [R w | w <- words, isRotonym w]
mapM_ (putStrLn . show) (S.elems rots)
Sticking Rotonym
instances in a set requires them to be instances of Ord
and Eq
:
instance Eq Rotonym where
(R w1) == (R w2) =
let r1 = rot13 w1
r2 = rot13 w2
in (w1 == w2 && r1 == r2) || (w1 == r2 && w2 == r1)
instance Ord Rotonym where
compare (R w1) (R w2) =
let r1 = rot13 w1
r2 = rot13 w2
in compare (length w1, (min w1 r1)) (length w2, (min w2 r2))
dmwit pointed out that what is actually going on here is taking an intersection of the the words and their rotated counterparts. This means the main
could be written
main = readFile "WORD.LST" >>=
mapM_ (putStrLn . show) . S.toList . S.map R . findRotonyms . S.fromList . lines
where findRotonyms ws = ws `S.intersection` (S.map rot13 ws)
Another idea that dmwit came up with was to introduce a class for rot13:
class Rot13 a where
rot13 :: a -> a
Char
is an instance of that class with the expected implementation of rot13
:
instance Rot13 Char where
rot13 c = chr ((ord c - ord 'a' + 13) `mod` (ord 'z' - ord 'a' + 1) + ord 'a')
If a
is an instance of Rot13
then list of a
is as well, again with the expected implementation:
instance (Rot13 a) => Rot13 [a] where
rot13 = map rot13
It is possible to intersect lists (Data.List.intersect
) but it turned out to be painfully slow, so back to sets again. A set of a
is an instance of Rot13
:
instance (Ord a, Rot13 a) => Rot13 (S.Set a) where
rot13 = S.map rot13
Finding all rotonyms is then straight forward:
main = readFile "WORD.LST" >>=
mapM_ (putStrLn . show) . S.toList . S.map R . findRotonyms . S.fromList . lines
where findRotonyms ws = ws `S.intersection` (rot13 ws)