There’ll be new dreams maybe better dreams and plenty
Before the last revolving year is through
http://jonimitchell.com/music/song.cfm?id=39
So what will be my new dreams? Am I turning my last page very soon?
Je crois entendre encore
Je crois la voir encore,
Je crois entendre encore,
My French is as bad as my CW, but both give me a tremendous joy. The same can be said
for my Russian and Haskell.
Haskell and Morse code
http://apfelmus.nfshost.com/articles/fun-with-morse-code.html
First, we use an association list.
text = "-.-. --.- @ -.. . @ .--- .... .---- --- --- -.. @ -.-"
dict :: [(String, Char)]
dict =
[(".-" ,'a'),
("-..." ,'b'),
("-.-." ,'c'),
("-.." ,'d'),
("." ,'e'),
("..-." ,'f'),
("--." ,'g'),
("...." ,'h'),
(".." ,'i'),
(".---" ,'j'),
("-.-" ,'k'),
(".-.." ,'l'),
("--" ,'m'),
("-." ,'n'),
("---" ,'o'),
(".--." ,'p'),
("--.-" ,'q'),
(".-." ,'r'),
("..." ,'s'),
("-" ,'t'),
("..-" ,'u'),
("...-" ,'v'),
(".--" ,'w'),
("-..-" ,'x'),
("-.--" ,'y'),
("--.." ,'z'),
("-----",'0'),
(".----",'1'),
("..---",'2'),
("...--",'3'),
("....-",'4'),
(".....",'5'),
("-....",'6'),
("--...",'7'),
("---..",'8'),
("----.",'9'),
("@" ,' ')]
decodeLetter :: String -> Char
decodeLetter code = maybe ' ' id $ lookup code dict
decode = map decodeLetter . words
main = do
print $ decode text
The function words breaks a string up into a list of words, which were delimited by
white space.
-- https://www.haskell.org/onlinereport/standard-prelude.html
words :: String -> [String]
words s = case dropWhile Char.isSpace s of
"" -> []
s' -> w : words s''
where (w, s'') = break Char.isSpace s'
Using a string “@” for a word space is not elegant, and there should be a better way.
The output will be:
"cq de jh1ood k"
Haskell and the Tower of Hanoi
https://en.wikipedia.org/wiki/Tower_of_Hanoi
hanoi :: Integer -> String -> String -> String -> [(String, String)] hanoi 0 _ _ _ = [] hanoi n a b c = hanoi (n-1) a c b ++ [(a, b)] ++ hanoi (n-1) c b a hanoiIO n = mapM_ f $ hanoi n "Pole 1" "Pole 3" "Pole 2" where f (x,y) = putStrLn $ "Move from " ++ show x ++ " to " ++ show y main = do hanoiIO 3
Move from "Pole 1" to "Pole 3" Move from "Pole 1" to "Pole 2" Move from "Pole 3" to "Pole 2" Move from "Pole 1" to "Pole 3" Move from "Pole 2" to "Pole 1" Move from "Pole 2" to "Pole 3" Move from "Pole 1" to "Pole 3"
Haskell and N-queens problem (2)
The function sameDiag is somewhat enigmatic. So I rewrite it as:
queens :: Int -> [[Int]]
queens n = filter test (generate n)
where generate 0 = [[]]
generate k = [q : qs | q <- [1..n], qs <- generate (k-1)]
test [] = True
test (q:qs) = isSafe q qs && test qs
isSafe try qs = not (try `elem` qs
|| try `elem` zipWith (+) qs [1..]
|| try `elem` zipWith (-) qs [1..])
-- isSafe try qs = not (try `elem` qs || sameDiag try qs)
-- sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs
main = do
print $ queens 4
[[2,4,1,3],[3,1,4,2]]
The function zipWith makes a list, its elements are calculated from the function
(+) and the elements of input lists, qs and [1..], occurring at the same position in both lists.
For example:
% ghci GHCi, version 7.10.3 Prelude> [1,3,2,4] [1,3,2,4] Prelude> zip [1,3,2,4][1..] [(1,1),(3,2),(2,3),(4,4)] Prelude> zipWith (+) [1,3,2,4][1..] [2,5,5,8]
The two same numbers, 5, in the obtained list [2,5,5,8] tells you that the queens on (b,3) and (c,2) are in the same diagonal, thus the arrangement [1,3,2,4] should fail the test.
Haskell and N-queens problem
https://en.wikipedia.org/wiki/Eight_queens_puzzle
This is a very popular problem, and let’s see how it can be treated with Haskell.
https://wiki.haskell.org/99_questions/Solutions/90
First, we generate all possible arrangements recursively.
queens :: Int -> [[Int]]
queens n = generate n
where generate 0 = [[]]
generate k = [q : qs | q <- [1..n], qs <- generate (k-1)]
main = do
print $ queens 3
[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]
Here, [x,y,z] means we have queens at (a,x), (b,y), (c,z).
Obviously, we can place only one queen for each raw, so the patters containing the same number must be eliminated.
queens :: Int -> [[Int]]
queens n = filter test (generate n)
where generate 0 = [[]]
generate k = [q : qs | q <- [1..n], qs <- generate (k-1)]
test [] = True
test (q:qs) = isSafe q qs && test qs
isSafe try qs = not (try `elem` qs)
main = do
print $ queens 3
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
The function elm returns True if the list qs contains an item equal to the argument try.
Now, the last thing to check is if the two queens are in the same diagonal.
queens :: Int -> [[Int]]
queens n = filter test (generate n)
where generate 0 = [[]]
generate k = [q : qs | q <- [1..n], qs <- generate (k-1)]
test [] = True
test (q:qs) = isSafe q qs && test qs
isSafe try qs = not (try `elem` qs || sameDiag try qs)
sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs
main = do
print $ queens 3
[ ]
This is OK, because we know that there is no solution for n=3. So let’s try again with n=4.
[[2,4,1,3],[3,1,4,2]]
Haskell
This is my first functional programming language.
% cat test.hs
main = do
putStrLn "CQ de JH1OOD"
% ghc -o test test.hs
[1 of 1] Compiling Main ( test.hs, test.o )
Linking test ...
% ./test
CQ de JH1OOD
% ghci
GHCi, version 7.10.3
Prelude> let fact :: Int -> Int; fact n = if n == 0 then 1 else n * fact (n-1)
Prelude> fact 10
3628800
Prelude> fact 20
2432902008176640000
% cat fact.hs
fact :: Integer -> Integer
fact n = if n == 0 then 1 else n * fact (n-1)
main = do
print $ fact 30
% ghc -o fact fact.hs
[1 of 1] Compiling Main ( fact.hs, fact.o )
Linking fact ...
% ./fact
265252859812191058636308480000000
% cat fibo.hs
fibo :: Integer -> Integer
fibo 0 = 0
fibo 1 = 1
fibo n = fibo (n-2) + fibo (n-1)
main = do
print $ fibo 20
% ghc -o fibo fibo.hs && ./fibo
6765
The Go Programming Language
There are so many languages, both computer and natural, in the world.
% cat hello-world.go
package main
import (
"fmt"
)
func main() {
fmt.Print("CQ de JH1OOD K\n")
}
% go run hello-world.go
CQ de JH1OOD K
% go build hello-world.go
% ./hello-world
CQ de JH1OOD K