Notes from 11 Sep
The notes from 9/9 have a recursive implementation of
pow that loops
(and multiplies) \(n\) times if the exponent is \(n\). (You can see the
pow 2 6 in those notes.)
We can do much better using a “fast exponentiation” algorithm, which distinguishes between even and odd exponents. Here it is:
square x = x*x fpow x n | n < 0 = error "Negative argument" | n == 0 = 1 | even n = fpow (square x) (n `div` 2) | otherwise = x * fpow x (n-1)
Here is a trace of this faster technique, on the same arguments:
fpow 2 6 ↝ [even] fpow (square 2) 3 ↝ fpow 4 3 ↝ [odd] 4 * fpow 4 2 ↝ [even] 4 * fpow (square 4) 1 ↝ 4 * fpow 16 1 ↝ 4 * 16 * fpow 16 0 ↝ [zero] 4 * 16 * 1 ↝ 64 * 1 ↝ 64
More flexible palindrome detection
One simple solution to the palindrome problem on assignment 1 is just this:
palindrome str = str == reverse str
That works fine for
racecar, but it might be nice to detect
palindromes where the case, spacing, and punctuation vary. Here’s what
we came up with:
palindrome str = s == reverse s where s = filter isAlpha (map toLower str)
λ> palindrome "Was it a car or a cat I saw?" True
More sophisticated ciphers
We pursued a generalization of
rot13 on the assignment, where the
number of steps to rotate could be a parameter.
alpha = ['a'..'z'] rot k c = if little `elem` front then chr (ord c + safeK) else if little `elem` back then chr (ord c - diff) else c where little = toLower c safeK = k `mod` 26 diff = 26 - safeK (front, back) = splitAt diff alpha
splitAt is just doing
drop at the same time. The
safeK represents the offset
k being clamped to the range
[0..25]. Let’s look at the example where
λ> splitAt 21 alpha ("abcdefghijklmnopqrstu","vwxyz") λ> chr (ord 'e' + 5) 'j' λ> chr (ord 's' + 5) 'x' λ> chr (ord 'x' - 21) 'c'
It’s always moving forward by 5 characters. If we start in the back segment of the alphabet (as with =’x’), then the effect of subtracting 21 is rotating around.
We can reproduce the effect of the hard-coded
rot 13 with
λ> map (rot 13) "Hello" "Uryyb" λ> map (rot 13) "Uryyb" "Hello"
But we can also use other pairs to encode/decode, including negative numbers.
λ> map (rot 5) "Testing" "Yjxynsl" λ> map (rot (-5)) "Yjxynsl" "Testing"
The next step we took still deserves some explanation, but I’ll reproduce it here. We don’t need to keep the rotation offset constant, but instead it can change with each character:
λ> zipWith rot [1..] "apple" "brspj"
This rotates the first letter by one position, second letter by two,
third letter by three, etc. That way, the two
'p' characters in
"apple" actually encode to different letters (
A more secure code would use a random sequence of numbers that either never repeats (called a one-time pad) or that repeats with a long period. Let’s say you and your friend randomly choose this sequence of numbers:
λ> secret = cycle [21, 13, 2, 5, 11, 6, 25, 8]
cycle function just repeats those over and over:
λ> take 20 secret [21,13,2,5,11,6,25,8,21,13,2,5,11,6,25,8,21,13,2,5]
Now you can encode and decode a secret message like this:
λ> zipWith rot secret "Cryptography is really fun" "Xeaueufzvcjd or mrcqwe npa" λ> zipWith rot (map negate secret) "Xeaueufzvcjd or mrcqwe npa" "Cryptography is really fun"