https://wiki.haskell.org/api.php?action=feedcontributions&user=Fis&feedformat=atomHaskellWiki - User contributions [en]2021-07-30T14:51:09ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=FFI_Introduction&diff=29753FFI Introduction2009-08-26T18:24:51Z<p>Fis: </p>
<hr />
<div>[[Category:Tutorials]]<br />
<br />
Haskell's FFI is used to call functions from other languages (basically C at this point), and for C to call haskell functions.<br />
<br />
== Links ==<br />
<br />
* [[Definition#Addenda to the report]] has the official description of the FFI.<br />
* [[FFI cook book]] has useful examples.<br />
* [http://www.haskell.org/greencard/ http://www.haskell.org/greencard/] the greencard FFI preprocessor generates FFI code for you. the links section lists a lot of alternatives. <br />
<br />
== Short version ==<br />
<br />
There are many more useful examples in the [[FFICookBook]], but here's a few basic ones:<br />
<br />
<haskell><br />
{-# INCLUDE <math.h> #-}<br />
{-# LANGUAGE ForeignFunctionInterface #-}<br />
module FfiExample where<br />
import Foreign.C -- get the C types<br />
<br />
-- pure function<br />
-- "unsafe" means it's slightly faster but can't callback to haskell<br />
foreign import ccall unsafe "sin" c_sin :: CDouble -> CDouble<br />
sin :: Double -> Double<br />
sin d = realToFrac (c_sin (realToFrac d))<br />
</haskell><br />
<br />
Note that the FFI document recommends putting the header in the double quotes, like<br />
<br />
<haskell><br />
foreign import ccall unsafe "math.h sin" c_sin :: CDouble -> CDouble<br />
</haskell><br />
<br />
However, the GHC docs say the pragma is "the Right Way" [ ''any technical reasons for this?'' ], and in practice most foreign imports will come from a small set of headers and it's easier to write them once at the top of the file.<br />
<br />
Notice that C types are not the same as haskell types, and you have to import them from Foreign.C. Notice also that, as usual in haskell, you have to explicitly convert to and from haskell types. Using c_<name_of_c_function> for the raw C function is just my convention.<br />
<br />
The haskell report only guarantees that Int has 30 bits of signed precision, so converting CInt to Int is not safe! On the other hand, many classes have instances for Int and Integer but not CInt, so it's generally more convenient to convert from the C types. To convert, I suppose you could either write a <code>checkedFromIntegral</code> function if you're sure it's small or just use Integer.<br />
<br />
For details on impure functions, pointers to objects, etc., see the cookbook.<br />
<br />
== Marshalling and unmarshalling arguments ==<br />
<br />
See the cookbook. It's nicer to do the marshalling and unmarshalling in haskell, but it's still low-level repetetive stuff. The functions are all available below Foreign, which supports memory allocation and pointers (and hence C arrays and "out" parameters). One thing it ''doesn't'' support is structs.<br />
<br />
Tools like GreenCard were created to help with this (as well as the low-level boilerplate thing).<br />
<br />
[ ''TODO: more detail here? examples in greencard?'' ]<br />
<br />
== Compiling FFI-using modules ==<br />
<br />
=== GHC ===<br />
<br />
Here's a makefile fragment to compile an FfiExample module that uses C functions from c_functions.c, which uses library functions from libcfuncs:<br />
<br />
<pre><br />
HFLAGS=-I/path/to/lib/include -L/path/to/lib<br />
<br />
_dummy_target: c_functions.o c_functions.h<br />
ghc $(HFLAGS) -main-is FfiExample --make -o ffi_example c_functions.o -lcfuncs<br />
</pre><br />
<br />
Notice the use of _dummy_target and --make. The idea is that you get make to compile what is necessary for C, and then always run ghc with --make, at which point it will figure out what is necessary to compile for haskell.<br />
<br />
Actually, this is broken, because ghc --make will not notice if a .o file has changed!<br />
<br />
[ ''this is just my hack, anyone have a better way to do this?'' ] <br />
<br />
=== Other compilers ===<br />
<br />
''Fill me in!''<br />
<br />
== Complete example with GHC ==<br />
<br />
GHC's libs don't (apparently?) support generic termios stuff. I could implement the whole tcgetattr / tcsetattr thing, but let's just turn ICANON on and off, so IO.getChar doesn't wait for a newline:<br />
<br />
termops.c:<br />
<br />
<pre><br />
#include <termios.h><br />
#include "termops.h"<br />
<br />
void<br />
set_icanon(int fd)<br />
{<br />
struct termios term;<br />
tcgetattr(0, &term);<br />
term.c_lflag |= ICANON;<br />
tcsetattr(fd, TCSAFLUSH, &term);<br />
}<br />
<br />
<br />
void<br />
unset_icanon(int fd)<br />
{<br />
struct termios term;<br />
tcgetattr(0, &term);<br />
term.c_lflag &= ~ICANON;<br />
tcsetattr(fd, TCSAFLUSH, &term);<br />
}<br />
</pre><br />
<br />
termops.h:<br />
<br />
<pre><br />
void set_icanon(int fd);<br />
void unset_icanon(int fd);<br />
</pre><br />
<br />
Termios.hs:<br />
<br />
<haskell><br />
{-# INCLUDE <termios.h> #-}<br />
{-# INCLUDE "termops.h" #-}<br />
{-# LANGUAGE ForeignFunctionInterface #-}<br />
module Termios where<br />
import Foreign.C<br />
<br />
foreign import ccall "set_icanon" set_icanon :: CInt -> IO ()<br />
foreign import ccall "unset_icanon" unset_icanon :: CInt -> IO ()<br />
<br />
</haskell><br />
<br />
FfiEx.hs:<br />
<br />
<haskell><br />
module FfiEx where<br />
import Control.Exception<br />
import System.IO<br />
import qualified Termios<br />
<br />
main = bracket_ (Termios.unset_icanon 0) (Termios.set_icanon 0)<br />
(while_true prompt)<br />
<br />
while_true op = do<br />
continue <- op<br />
if continue then while_true op else return ()<br />
<br />
prompt = do<br />
putStr "? "<br />
hFlush stdout<br />
c <- getChar<br />
putStrLn $ "you typed " ++ [c]<br />
return (c /= 'q')<br />
</haskell><br />
<br />
makefile:<br />
<br />
<pre><br />
_ffi_ex: termops.o<br />
ghc --make -main-is FfiEx -o ffi_ex FfiEx.hs termops.o<br />
</pre><br />
<br />
[this only worked for me when I omitted termops.o at the end of the `ghc --make` command. Seems like it searches for and finds the .o automatically? --lodi ]<br />
<br />
<br />
And now:<br />
<br />
<pre><br />
<br />
% make<br />
gcc -c -o termops.o termops.c<br />
ghc --make -main-is FfiEx -o ffi_ex FfiEx.hs termops.o<br />
[1 of 2] Compiling Termios ( Termios.hs, Termios.o )<br />
[2 of 2] Compiling FfiEx ( FfiEx.hs, FfiEx.o )<br />
Linking ffi_ex ...<br />
% ./ffi_ex<br />
? you typed a<br />
? you typed b<br />
? you typed q<br />
%<br />
</pre></div>Fishttps://wiki.haskell.org/index.php?title=Heterogenous_collections&diff=8391Heterogenous collections2006-11-17T18:49:30Z<p>Fis: </p>
<hr />
<div>This page is a very hasty and ad-hoc summary of a common discussion on<br />
the haskell-cafe list. If you find it hard to read, please complain<br />
there and somebody hopefully will come to help.<br />
<br />
<br />
=== The problem ===<br />
<br />
Is some kind of collection of object with different types in Haskell<br />
exist? Except the tuples, which have fixed length. I find this<br />
<br />
* Tuples heterogeneous, lists homogeneous.<br />
* Tuples have a fixed length, or at least their length is encoded in their type. That is, two tuples with different lengths will have different types.<br />
* Tuples always finite.<br />
<br />
But I need something which is heterogeneous and non-fixed length. I'm<br />
used do Java, and this switch to functional languages is very strange to<br />
me. So, to be clear, I need something like LinkedList<Object> in java.<br />
<br />
<br />
=== Algebraic Datatypes ===<br />
<br />
If the number of types to cover is fixed, then I suggest a data type<br />
like<br />
<br />
<haskell><br />
data T =<br />
ConsInt Int<br />
| ConsString String<br />
| ConsChar Char<br />
</haskell><br />
<br />
or:<br />
<br />
<haskell><br />
data Object = IntObject Int | StringObject String<br />
<br />
objectString :: Object -> String<br />
objectString (IntObject v) = show v<br />
objectString (StringObject v) = v<br />
<br />
main = mapM (putStrLn . objectString) [(IntObject 7), (StringObject "eight")]<br />
</haskell><br />
<br />
This is a very basic solution, and often preferable. Limitations: You<br />
have to type-switch all the time if you want to do anything with the<br />
objects in the List, and the collections are clumsy to extend by new<br />
types.<br />
<br />
<br />
<br />
=== HLists, OOHaskell, Type-Level Programming ===<br />
<br />
This is the cleanest solution, but very advanced and a little<br />
restrictive. Read these two articles:<br />
<br />
* http://homepages.cwi.nl/~ralf/HList/<br />
* http://homepages.cwi.nl/~ralf/OOHaskell/<br />
<br />
There is also some related material here:<br />
<br />
* http://www.haskell.org/haskellwiki/Extensible_record<br />
<br />
<br />
=== Existential Types ===<br />
<br />
Depending on your needs and your comfort level with fancier types, the<br />
existential approach to ADTs might solve your problem. The following<br />
code is a demonstration you can cut-and-paste-and-run.<br />
<br />
This is example akin to upcasting in Java to an interface that lets<br />
you print things. That way you know how to print every object (or do<br />
whatever else it is you need to do) in the list. Beware: there is no<br />
safe downcasting (that's what Typeable would be for); that would<br />
likely be more than you need.<br />
<br />
There are other ways to do this with existentials (e.g. bounded<br />
existentials), but this is what came out of my head when I read your<br />
post. Existentials seems to be the "Haskellish" way to reduce a<br />
hetergenous list to a collection of objects with common operations.<br />
HList would be the Haskellish way for more static and flexible<br />
assurances.<br />
<br />
<haskell><br />
{-# OPTIONS -fglasgow-exts #-}<br />
<br />
module Test where<br />
<br />
data PrintPackage = forall a . PrintPackage a (a -> String)<br />
<br />
instance Show PrintPackage where<br />
show (PrintPackage val showMethod) = showMethod val<br />
<br />
list = [ PrintPackage 3 show<br />
, PrintPackage "string" show<br />
, PrintPackage 3.4 show<br />
]<br />
<br />
main = print list<br />
</haskell></div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Secret_Santas/Solution_Matthias&diff=7345Haskell Quiz/Secret Santas/Solution Matthias2006-10-26T11:59:31Z<p>Fis: </p>
<hr />
<div>[[Category:Code]]<br />
<br />
this program takes embarassingly long to answer, even for the seven people from the puzzle. but writing it down was easy. rather than computing all results and picking a random one, i think function f should shuffle santas and victims, and then take the first valid solution returned by q. this here works, though, so i'll bail out.<br />
<br />
note that the algorithm itself, without parsing, output, and selection of a random solution, takes only 16 short lines, comments and type signatures included!<br />
<br />
<haskell><br />
module Main where<br />
import Monad<br />
import List<br />
import Random<br />
<br />
data P = P String String String deriving (Show, Eq, Ord)<br />
<br />
parseP :: String -> P<br />
parseP s = f "" s<br />
where<br />
f acc (' ':s) = case g "" s of (lastname, email) -> P (reverse acc) lastname email<br />
f acc (c:s) = f (c:acc) s<br />
<br />
g acc (' ':s) = (reverse acc, s)<br />
g acc (c:s) = g (c:acc) s<br />
<br />
showPs :: [(P, P)] -> String<br />
showPs = join . map (\ (santa, victim) -> show santa ++ " is secrect santa for " ++ show victim ++ "\n")<br />
<br />
main :: IO ()<br />
main = getContents >>= g >>= putStr . showPs<br />
<br />
g :: String -> IO [(P, P)] -- parse input<br />
g i = let k = map parseP $ lines i in f k k<br />
<br />
f :: [P] -> [P] -> IO [(P, P)] -- compute output<br />
f santas victims = do<br />
let all = q [] santas victims<br />
i <- randomRIO (0, length all - 1)<br />
return (all !! i)<br />
<br />
-- q takes a partial solution, a pool of remaining santas, and a pool of remaining victims. it then produces all<br />
-- possible next matches, calls itself recursively, and returns the complete set of all solutions.<br />
<br />
q :: [(P, P)] -> [P] -> [P] -> [[(P, P)]]<br />
q acc [] [] = [acc] -- (found a valid solution)<br />
q acc [] _ = [] -- leftover victims<br />
q acc _ [] = [] -- leftover santas<br />
q acc santas victims = [ tl | santa <- santas,<br />
victim <- victims,<br />
matchOk santa victim,<br />
tl <- q ((santa, victim) : acc)<br />
(santas \\ [santa])<br />
(victims \\ [victim]) ]<br />
<br />
matchOk :: P -> P -> Bool<br />
matchOk (P _ santa _) (P _ victim _) = santa /= victim<br />
</haskell></div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Secret_Santas/Solution_Matthias&diff=7344Haskell Quiz/Secret Santas/Solution Matthias2006-10-26T11:59:13Z<p>Fis: </p>
<hr />
<div>[[Category:Code]]<br />
<br />
this program takes embarassingly long to answer, even for the seven people from the puzzle. but writing it down was easy. rather than computing all results and picking a random one, i think function f should shuffle santas and victims, and then take the first valid solution returned by q. this here works, though, so i'll bail out.<br />
<br />
(note that the algorithm itself, without parsing, output, and selection of a random solution, takes only 16 short lines, comments and type signatures included!<br />
<br />
<haskell><br />
module Main where<br />
import Monad<br />
import List<br />
import Random<br />
<br />
data P = P String String String deriving (Show, Eq, Ord)<br />
<br />
parseP :: String -> P<br />
parseP s = f "" s<br />
where<br />
f acc (' ':s) = case g "" s of (lastname, email) -> P (reverse acc) lastname email<br />
f acc (c:s) = f (c:acc) s<br />
<br />
g acc (' ':s) = (reverse acc, s)<br />
g acc (c:s) = g (c:acc) s<br />
<br />
showPs :: [(P, P)] -> String<br />
showPs = join . map (\ (santa, victim) -> show santa ++ " is secrect santa for " ++ show victim ++ "\n")<br />
<br />
main :: IO ()<br />
main = getContents >>= g >>= putStr . showPs<br />
<br />
g :: String -> IO [(P, P)] -- parse input<br />
g i = let k = map parseP $ lines i in f k k<br />
<br />
f :: [P] -> [P] -> IO [(P, P)] -- compute output<br />
f santas victims = do<br />
let all = q [] santas victims<br />
i <- randomRIO (0, length all - 1)<br />
return (all !! i)<br />
<br />
-- q takes a partial solution, a pool of remaining santas, and a pool of remaining victims. it then produces all<br />
-- possible next matches, calls itself recursively, and returns the complete set of all solutions.<br />
<br />
q :: [(P, P)] -> [P] -> [P] -> [[(P, P)]]<br />
q acc [] [] = [acc] -- (found a valid solution)<br />
q acc [] _ = [] -- leftover victims<br />
q acc _ [] = [] -- leftover santas<br />
q acc santas victims = [ tl | santa <- santas,<br />
victim <- victims,<br />
matchOk santa victim,<br />
tl <- q ((santa, victim) : acc)<br />
(santas \\ [santa])<br />
(victims \\ [victim]) ]<br />
<br />
matchOk :: P -> P -> Bool<br />
matchOk (P _ santa _) (P _ victim _) = santa /= victim<br />
</haskell></div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Secret_Santas&diff=7343Haskell Quiz/Secret Santas2006-10-26T11:55:51Z<p>Fis: </p>
<hr />
<div>[[Category:Code]]<br />
<br />
==The problem==<br />
<br />
* http://www.rubyquiz.com/quiz2.html<br />
<br />
<br />
==Solutions==<br />
<br />
* [[Haskell Quiz/Secret Santas/Solution Matthias|Matthias]]</div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz&diff=7342Haskell Quiz2006-10-26T11:53:01Z<p>Fis: </p>
<hr />
<div>A collection of solutions to the [http://www.rubyquiz.com Ruby quiz] puzzles in simple, elegant Haskell.<br />
<br />
As you solve the puzzles, please contribute your code, and create a page<br />
for the puzzle entries. When creating a new page for your source, be<br />
sure to categorise it as code, with a [ [ Category:Code ] ] tag.<br />
<br />
== The Puzzles ==<br />
<br />
1. [[Haskell Quiz/The Solitaire Cipher|The Solitaire Cipher]]<br />
<br />
2. [[Haskell Quiz/Secret Santas|Secret Santas]]<br />
<br />
31. [[Haskell Quiz/Amazing Mazes|Amazing Mazes]]<br />
<br />
[[Category:Code]]</div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher/Solution_Matthias&diff=7320Haskell Quiz/The Solitaire Cipher/Solution Matthias2006-10-26T07:23:06Z<p>Fis: </p>
<hr />
<div><haskell><br />
module Main where<br />
import Maybe<br />
import Monad<br />
import Char<br />
import List<br />
import Control.Exception<br />
import Control.Monad.ST<br />
import Data.STRef<br />
<br />
{-<br />
carelessly written. i haven't looked much at the discussion or at the other<br />
solutions, so there is certainly room for improvent, cleanup, and completion.<br />
also it would be nice to make it less than three billion times slower than<br />
a straight-forward C implementation (how much would it help merely to use<br />
immutable arrays?)<br />
-}<br />
<br />
----------------------------------------------------------------------<br />
-- the deck<br />
<br />
data Suit = Clubs | Diamonds | Hearts | Spades<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Suit where<br />
toEnum 0 = Clubs<br />
toEnum 1 = Diamonds<br />
toEnum 2 = Hearts<br />
toEnum 3 = Spades<br />
toEnum i = error ("enum Suit: " ++ show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 3]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 3]<br />
<br />
fromEnum Clubs = 0<br />
fromEnum Diamonds = 1<br />
fromEnum Hearts = 2<br />
fromEnum Spades = 3<br />
<br />
data Base = Ace | Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Base where<br />
toEnum 1 = Ace<br />
toEnum 2 = Two<br />
toEnum 3 = Three<br />
toEnum 4 = Four<br />
toEnum 5 = Five<br />
toEnum 6 = Six<br />
toEnum 7 = Seven<br />
toEnum 8 = Eight<br />
toEnum 9 = Nine<br />
toEnum 10 = Ten<br />
toEnum 11 = Jack<br />
toEnum 12 = Queen<br />
toEnum 13 = King<br />
toEnum i = error ("enum Base: " ++ show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 13]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 13]<br />
<br />
fromEnum Ace = 1<br />
fromEnum Two = 2<br />
fromEnum Three = 3<br />
fromEnum Four = 4<br />
fromEnum Five = 5<br />
fromEnum Six = 6<br />
fromEnum Seven = 7<br />
fromEnum Eight = 8<br />
fromEnum Nine = 9<br />
fromEnum Ten = 10<br />
fromEnum Jack = 11<br />
fromEnum Queen = 12<br />
fromEnum King = 13<br />
<br />
data Card = Card Base Suit | JokerA | JokerB<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Card where<br />
fromEnum JokerA = 53<br />
fromEnum JokerB = 53<br />
fromEnum (Card base suit) = fromEnum base + (fromEnum suit * 13)<br />
<br />
toEnum 53 = error "Jokers break instance Enum Card."<br />
toEnum i | i >= 1 && i <= 52 = Card (toEnum ((i - 1) `mod` 13 + 1)) (toEnum ((i - 1) `div` 13))<br />
toEnum i = error (show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 52] ++ [JokerA, JokerB]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 52] ++ [JokerA, JokerB]<br />
<br />
isJoker :: Card -> Bool<br />
isJoker = (`elem` [JokerA, JokerB])<br />
<br />
type Deck = [Card]<br />
<br />
isDeck d = sort d == deck<br />
<br />
deck :: [Card]<br />
deck = [Card Ace Clubs ..]<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- a few auxiliary transformations<br />
<br />
cardToLetter :: Card -> Char<br />
cardToLetter JokerA = error "cardToLetter: please don't convert jokers to letters."<br />
cardToLetter JokerB = error "cardToLetter: please don't convert jokers to letters."<br />
cardToLetter c = chr ((fromEnum c - 1) `mod` 26 + ord 'A')<br />
<br />
letterToCard :: Char -> Card<br />
letterToCard c<br />
| c <= 'A' || c >= 'Z' = error "letterToCard: only capitals [A-Z] can be converted into cards."<br />
| otherwise = toEnum (ord c - ord 'A' + 1)<br />
<br />
cleanupInput :: String -> [String]<br />
cleanupInput = groupN 5 'X' . catMaybes . map f<br />
where<br />
f c | ord c >= ord 'A' && ord c <= ord 'Z' = Just c<br />
| ord c >= ord 'a' && ord c <= ord 'z' = Just $ toUpper c<br />
| otherwise = Nothing<br />
<br />
groupN :: Int -> a -> [a] -> [[a]]<br />
groupN n pad = f n<br />
where<br />
f 0 xs = [] : f n xs<br />
f i (x:xs) = let (l:ls) = f (i-1) xs in (x:l):ls<br />
f i [] = if i < n then [replicate i pad] else []<br />
<br />
intersperseNth :: Int -> a -> [a] -> [a] -- we don't need that any more now, but it's still a cool funktion. (:<br />
intersperseNth n c = f n<br />
where<br />
f 0 xs = c : f n xs<br />
f i (x:xs) = x : f (i-1) xs<br />
f _ [] = []<br />
<br />
newXOR :: Char -> Card -> Char<br />
newXOR c o<br />
| c <= 'A' || c >= 'Z' = error ("newXOR: illegal character: " ++ show c)<br />
| isJoker o = error ("newXOR: illegal card: " ++ show o)<br />
| otherwise = let<br />
c' = ord c - ord 'A'<br />
o' = fromEnum o - 1<br />
in chr ((c' + o') `mod` 26 + 1)<br />
<br />
-- (It may also be interesting to write an instance of Num for Card, but let's see how far we get without one first...)<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- the stream<br />
<br />
-- circular moves: think of the deck as being a ring, not a list, and always move JokerA one card down, and JokerB two.<br />
<br />
moveA :: Deck -> Deck<br />
moveA = f []<br />
where<br />
f acc (JokerA : x : xs) = reverse acc ++ (x : JokerA : xs)<br />
f acc (JokerA : []) = last acc : JokerA : tail (reverse acc)<br />
f acc (x : xs) = f (x : acc) xs<br />
<br />
moveB :: Deck -> Deck<br />
moveB = f []<br />
where<br />
f acc (JokerB : x : y : ys) = reverse acc ++ (x : y : JokerB : ys)<br />
f acc (JokerB : x : []) = last acc : JokerB : tail (reverse (x : acc))<br />
f acc (JokerB : []) = case reverse acc of (a : b : ccc) -> a : b : JokerB : ccc<br />
f acc (x : xs) = f (x : acc) xs<br />
<br />
-- first triple cut: split at jokers and shuffle triples<br />
<br />
tripleCut :: Deck -> Deck<br />
tripleCut d = c ++ b ++ a<br />
where<br />
posA = fromJust $ findIndex (== JokerA) d<br />
posB = fromJust $ findIndex (== JokerB) d<br />
<br />
posTop = min posA posB<br />
posBot = max posA posB<br />
<br />
-- d == a ++ b@([Joker] ++ _ ++ [Joker]) ++ c<br />
<br />
a = take posTop d<br />
x = drop posTop d<br />
b = take (posBot - posTop + 1) x<br />
c = drop (posBot - posTop + 1) x<br />
<br />
-- triple cut<br />
<br />
countCut :: Deck -> Deck<br />
countCut d = lower ++ upper ++ [c]<br />
where<br />
c = last d<br />
(upper, lower) = splitAt (fromEnum c) (init d)<br />
<br />
-- extract the next stream symbol<br />
<br />
findSymbol :: Deck -> Card<br />
findSymbol d = d !! (fromEnum (head d))<br />
<br />
streamStep :: STRef s Deck -> ST s Char<br />
streamStep ref = do<br />
d <- readSTRef ref<br />
let d' = countCut . tripleCut . moveB . moveA $ d<br />
writeSTRef ref d'<br />
let s = findSymbol d'<br />
if isJoker s<br />
then streamStep ref<br />
else return $ cardToLetter s<br />
<br />
streamStart :: ST s (STRef s Deck)<br />
streamStart = newSTRef deck<br />
<br />
stream :: Integer -> Int -> String<br />
stream key len = runST (do<br />
ref <- streamStart<br />
d <- readSTRef ref<br />
writeSTRef ref $ keyDeck key d<br />
sequence . replicate len $ streamStep ref)<br />
<br />
testStream = stream 0 10 == "DWJXHYRFDG"<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- the algorithm frame<br />
<br />
-- and this is where i got bored... (-:<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- keying the deck<br />
<br />
keyDeck :: Integer -> Deck -> Deck<br />
keyDeck _ d = d -- (not yet)<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- testing<br />
<br />
test1 = "CLEPK HHNIY CFPWH FDFEH"<br />
test2 = "ABVAW LWZSY OORYK DUPVH"<br />
</haskell></div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher&diff=7319Haskell Quiz/The Solitaire Cipher2006-10-26T07:20:40Z<p>Fis: </p>
<hr />
<div>The first puzzle of the rubyquizz series was to implement the Solitaire cipher [http://en.wikipedia.org/wiki/Solitaire_(cipher)] Bruce Schneier made for Neil Stephenson's Cryptonomicon [http://en.wikipedia.org/wiki/Cryptonomicon]. The twist is that it's designed to be done by a Spy in a containment camp with no other tools than a deck of bridge cards.<br />
<br />
<b>The problem:</b><br />
<br />
* http://www.rubyquiz.com/quiz1.html<br />
* http://www.schneier.com/solitaire.html<br />
<br />
<b>Solutions:</b><br />
<br />
* [[Haskell Quiz/The Solitaire Cipher/Solution Don|Don]]<br />
* [[Haskell Quiz/The Solitaire Cipher/Solution Matthias|Matthias]]<br />
(incomplete, but stream generation works)</div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher/Solution_Matthias&diff=7318Haskell Quiz/The Solitaire Cipher/Solution Matthias2006-10-26T07:18:16Z<p>Fis: </p>
<hr />
<div><haskell><br />
module Main where<br />
import Maybe<br />
import Monad<br />
import Char<br />
import List<br />
import Control.Exception<br />
import Control.Monad.ST<br />
import Data.STRef<br />
<br />
{-<br />
<br />
carelessly written. i haven't looked much at the discussion or at the other<br />
solutions, so there is certainly room for improvent, cleanup, and completion.<br />
<br />
-}<br />
<br />
----------------------------------------------------------------------<br />
-- the deck<br />
<br />
data Suit = Clubs | Diamonds | Hearts | Spades<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Suit where<br />
toEnum 0 = Clubs<br />
toEnum 1 = Diamonds<br />
toEnum 2 = Hearts<br />
toEnum 3 = Spades<br />
toEnum i = error ("enum Suit: " ++ show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 3]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 3]<br />
<br />
fromEnum Clubs = 0<br />
fromEnum Diamonds = 1<br />
fromEnum Hearts = 2<br />
fromEnum Spades = 3<br />
<br />
data Base = Ace | Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Base where<br />
toEnum 1 = Ace<br />
toEnum 2 = Two<br />
toEnum 3 = Three<br />
toEnum 4 = Four<br />
toEnum 5 = Five<br />
toEnum 6 = Six<br />
toEnum 7 = Seven<br />
toEnum 8 = Eight<br />
toEnum 9 = Nine<br />
toEnum 10 = Ten<br />
toEnum 11 = Jack<br />
toEnum 12 = Queen<br />
toEnum 13 = King<br />
toEnum i = error ("enum Base: " ++ show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 13]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 13]<br />
<br />
fromEnum Ace = 1<br />
fromEnum Two = 2<br />
fromEnum Three = 3<br />
fromEnum Four = 4<br />
fromEnum Five = 5<br />
fromEnum Six = 6<br />
fromEnum Seven = 7<br />
fromEnum Eight = 8<br />
fromEnum Nine = 9<br />
fromEnum Ten = 10<br />
fromEnum Jack = 11<br />
fromEnum Queen = 12<br />
fromEnum King = 13<br />
<br />
data Card = Card Base Suit | JokerA | JokerB<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Card where<br />
fromEnum JokerA = 53<br />
fromEnum JokerB = 53<br />
fromEnum (Card base suit) = fromEnum base + (fromEnum suit * 13)<br />
<br />
toEnum 53 = error "Jokers break instance Enum Card."<br />
toEnum i | i >= 1 && i <= 52 = Card (toEnum ((i - 1) `mod` 13 + 1)) (toEnum ((i - 1) `div` 13))<br />
toEnum i = error (show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 52] ++ [JokerA, JokerB]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 52] ++ [JokerA, JokerB]<br />
<br />
isJoker :: Card -> Bool<br />
isJoker = (`elem` [JokerA, JokerB])<br />
<br />
type Deck = [Card]<br />
<br />
isDeck d = sort d == deck<br />
<br />
deck :: [Card]<br />
deck = [Card Ace Clubs ..]<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- a few auxiliary transformations<br />
<br />
cardToLetter :: Card -> Char<br />
cardToLetter JokerA = error "cardToLetter: please don't convert jokers to letters."<br />
cardToLetter JokerB = error "cardToLetter: please don't convert jokers to letters."<br />
cardToLetter c = chr ((fromEnum c - 1) `mod` 26 + ord 'A')<br />
<br />
letterToCard :: Char -> Card<br />
letterToCard c<br />
| c <= 'A' || c >= 'Z' = error "letterToCard: only capitals [A-Z] can be converted into cards."<br />
| otherwise = toEnum (ord c - ord 'A' + 1)<br />
<br />
cleanupInput :: String -> [String]<br />
cleanupInput = groupN 5 'X' . catMaybes . map f<br />
where<br />
f c | ord c >= ord 'A' && ord c <= ord 'Z' = Just c<br />
| ord c >= ord 'a' && ord c <= ord 'z' = Just $ toUpper c<br />
| otherwise = Nothing<br />
<br />
groupN :: Int -> a -> [a] -> [[a]]<br />
groupN n pad = f n<br />
where<br />
f 0 xs = [] : f n xs<br />
f i (x:xs) = let (l:ls) = f (i-1) xs in (x:l):ls<br />
f i [] = if i < n then [replicate i pad] else []<br />
<br />
intersperseNth :: Int -> a -> [a] -> [a] -- we don't need that any more now, but it's still a cool funktion. (:<br />
intersperseNth n c = f n<br />
where<br />
f 0 xs = c : f n xs<br />
f i (x:xs) = x : f (i-1) xs<br />
f _ [] = []<br />
<br />
newXOR :: Char -> Card -> Char<br />
newXOR c o<br />
| c <= 'A' || c >= 'Z' = error ("newXOR: illegal character: " ++ show c)<br />
| isJoker o = error ("newXOR: illegal card: " ++ show o)<br />
| otherwise = let<br />
c' = ord c - ord 'A'<br />
o' = fromEnum o - 1<br />
in chr ((c' + o') `mod` 26 + 1)<br />
<br />
-- (It may also be interesting to write an instance of Num for Card, but let's see how far we get without one first...)<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- the stream<br />
<br />
-- circular moves: think of the deck as being a ring, not a list, and always move JokerA one card down, and JokerB two.<br />
<br />
moveA :: Deck -> Deck<br />
moveA = f []<br />
where<br />
f acc (JokerA : x : xs) = reverse acc ++ (x : JokerA : xs)<br />
f acc (JokerA : []) = last acc : JokerA : tail (reverse acc)<br />
f acc (x : xs) = f (x : acc) xs<br />
<br />
moveB :: Deck -> Deck<br />
moveB = f []<br />
where<br />
f acc (JokerB : x : y : ys) = reverse acc ++ (x : y : JokerB : ys)<br />
f acc (JokerB : x : []) = last acc : JokerB : tail (reverse (x : acc))<br />
f acc (JokerB : []) = case reverse acc of (a : b : ccc) -> a : b : JokerB : ccc<br />
f acc (x : xs) = f (x : acc) xs<br />
<br />
-- first triple cut: split at jokers and shuffle triples<br />
<br />
tripleCut :: Deck -> Deck<br />
tripleCut d = c ++ b ++ a<br />
where<br />
posA = fromJust $ findIndex (== JokerA) d<br />
posB = fromJust $ findIndex (== JokerB) d<br />
<br />
posTop = min posA posB<br />
posBot = max posA posB<br />
<br />
-- d == a ++ b@([Joker] ++ _ ++ [Joker]) ++ c<br />
<br />
a = take posTop d<br />
x = drop posTop d<br />
b = take (posBot - posTop + 1) x<br />
c = drop (posBot - posTop + 1) x<br />
<br />
-- triple cut<br />
<br />
countCut :: Deck -> Deck<br />
countCut d = lower ++ upper ++ [c]<br />
where<br />
c = last d<br />
(upper, lower) = splitAt (fromEnum c) (init d)<br />
<br />
-- extract the next stream symbol<br />
<br />
findSymbol :: Deck -> Card<br />
findSymbol d = d !! (fromEnum (head d))<br />
<br />
streamStep :: STRef s Deck -> ST s Char<br />
streamStep ref = do<br />
d <- readSTRef ref<br />
let d' = countCut . tripleCut . moveB . moveA $ d<br />
writeSTRef ref d'<br />
let s = findSymbol d'<br />
if isJoker s<br />
then streamStep ref<br />
else return $ cardToLetter s<br />
<br />
streamStart :: ST s (STRef s Deck)<br />
streamStart = newSTRef deck<br />
<br />
stream :: Integer -> Int -> String<br />
stream key len = runST (do<br />
ref <- streamStart<br />
d <- readSTRef ref<br />
writeSTRef ref $ keyDeck key d<br />
sequence . replicate len $ streamStep ref)<br />
<br />
testStream = stream 0 10 == "DWJXHYRFDG"<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- the algorithm frame<br />
<br />
-- and this is where i got bored... (-:<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- keying the deck<br />
<br />
keyDeck :: Integer -> Deck -> Deck<br />
keyDeck _ d = d -- (not yet)<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- testing<br />
<br />
test1 = "CLEPK HHNIY CFPWH FDFEH"<br />
test2 = "ABVAW LWZSY OORYK DUPVH"<br />
</haskell></div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher/Solution_Matthias&diff=7317Haskell Quiz/The Solitaire Cipher/Solution Matthias2006-10-26T07:16:48Z<p>Fis: </p>
<hr />
<div><pre><br />
module Main where<br />
import Maybe<br />
import Monad<br />
import Char<br />
import List<br />
import Control.Exception<br />
import Control.Monad.ST<br />
import Data.STRef<br />
<br />
{-<br />
<br />
carelessly written. i haven't looked much at the discussion or at the other<br />
solutions, so there is certainly room for improvent, cleanup, and completion.<br />
<br />
-}<br />
<br />
----------------------------------------------------------------------<br />
-- the deck<br />
<br />
data Suit = Clubs | Diamonds | Hearts | Spades<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Suit where<br />
toEnum 0 = Clubs<br />
toEnum 1 = Diamonds<br />
toEnum 2 = Hearts<br />
toEnum 3 = Spades<br />
toEnum i = error ("enum Suit: " ++ show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 3]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 3]<br />
<br />
fromEnum Clubs = 0<br />
fromEnum Diamonds = 1<br />
fromEnum Hearts = 2<br />
fromEnum Spades = 3<br />
<br />
data Base = Ace | Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Base where<br />
toEnum 1 = Ace<br />
toEnum 2 = Two<br />
toEnum 3 = Three<br />
toEnum 4 = Four<br />
toEnum 5 = Five<br />
toEnum 6 = Six<br />
toEnum 7 = Seven<br />
toEnum 8 = Eight<br />
toEnum 9 = Nine<br />
toEnum 10 = Ten<br />
toEnum 11 = Jack<br />
toEnum 12 = Queen<br />
toEnum 13 = King<br />
toEnum i = error ("enum Base: " ++ show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 13]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 13]<br />
<br />
fromEnum Ace = 1<br />
fromEnum Two = 2<br />
fromEnum Three = 3<br />
fromEnum Four = 4<br />
fromEnum Five = 5<br />
fromEnum Six = 6<br />
fromEnum Seven = 7<br />
fromEnum Eight = 8<br />
fromEnum Nine = 9<br />
fromEnum Ten = 10<br />
fromEnum Jack = 11<br />
fromEnum Queen = 12<br />
fromEnum King = 13<br />
<br />
data Card = Card Base Suit | JokerA | JokerB<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Card where<br />
fromEnum JokerA = 53<br />
fromEnum JokerB = 53<br />
fromEnum (Card base suit) = fromEnum base + (fromEnum suit * 13)<br />
<br />
toEnum 53 = error "Jokers break instance Enum Card."<br />
toEnum i | i >= 1 && i <= 52 = Card (toEnum ((i - 1) `mod` 13 + 1)) (toEnum ((i - 1) `div` 13))<br />
toEnum i = error (show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 52] ++ [JokerA, JokerB]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 52] ++ [JokerA, JokerB]<br />
<br />
isJoker :: Card -> Bool<br />
isJoker = (`elem` [JokerA, JokerB])<br />
<br />
type Deck = [Card]<br />
<br />
isDeck d = sort d == deck<br />
<br />
deck :: [Card]<br />
deck = [Card Ace Clubs ..]<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- a few auxiliary transformations<br />
<br />
cardToLetter :: Card -> Char<br />
cardToLetter JokerA = error "cardToLetter: please don't convert jokers to letters."<br />
cardToLetter JokerB = error "cardToLetter: please don't convert jokers to letters."<br />
cardToLetter c = chr ((fromEnum c - 1) `mod` 26 + ord 'A')<br />
<br />
letterToCard :: Char -> Card<br />
letterToCard c<br />
| c <= 'A' || c >= 'Z' = error "letterToCard: only capitals [A-Z] can be converted into cards."<br />
| otherwise = toEnum (ord c - ord 'A' + 1)<br />
<br />
cleanupInput :: String -> [String]<br />
cleanupInput = groupN 5 'X' . catMaybes . map f<br />
where<br />
f c | ord c >= ord 'A' && ord c <= ord 'Z' = Just c<br />
| ord c >= ord 'a' && ord c <= ord 'z' = Just $ toUpper c<br />
| otherwise = Nothing<br />
<br />
groupN :: Int -> a -> [a] -> [[a]]<br />
groupN n pad = f n<br />
where<br />
f 0 xs = [] : f n xs<br />
f i (x:xs) = let (l:ls) = f (i-1) xs in (x:l):ls<br />
f i [] = if i < n then [replicate i pad] else []<br />
<br />
intersperseNth :: Int -> a -> [a] -> [a] -- we don't need that any more now, but it's still a cool funktion. (:<br />
intersperseNth n c = f n<br />
where<br />
f 0 xs = c : f n xs<br />
f i (x:xs) = x : f (i-1) xs<br />
f _ [] = []<br />
<br />
newXOR :: Char -> Card -> Char<br />
newXOR c o<br />
| c <= 'A' || c >= 'Z' = error ("newXOR: illegal character: " ++ show c)<br />
| isJoker o = error ("newXOR: illegal card: " ++ show o)<br />
| otherwise = let<br />
c' = ord c - ord 'A'<br />
o' = fromEnum o - 1<br />
in chr ((c' + o') `mod` 26 + 1)<br />
<br />
-- (It may also be interesting to write an instance of Num for Card, but let's see how far we get without one first...)<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- the stream<br />
<br />
-- circular moves: think of the deck as being a ring, not a list, and always move JokerA one card down, and JokerB two.<br />
<br />
moveA :: Deck -> Deck<br />
moveA = f []<br />
where<br />
f acc (JokerA : x : xs) = reverse acc ++ (x : JokerA : xs)<br />
f acc (JokerA : []) = last acc : JokerA : tail (reverse acc)<br />
f acc (x : xs) = f (x : acc) xs<br />
<br />
moveB :: Deck -> Deck<br />
moveB = f []<br />
where<br />
f acc (JokerB : x : y : ys) = reverse acc ++ (x : y : JokerB : ys)<br />
f acc (JokerB : x : []) = last acc : JokerB : tail (reverse (x : acc))<br />
f acc (JokerB : []) = case reverse acc of (a : b : ccc) -> a : b : JokerB : ccc<br />
f acc (x : xs) = f (x : acc) xs<br />
<br />
-- first triple cut: split at jokers and shuffle triples<br />
<br />
tripleCut :: Deck -> Deck<br />
tripleCut d = c ++ b ++ a<br />
where<br />
posA = fromJust $ findIndex (== JokerA) d<br />
posB = fromJust $ findIndex (== JokerB) d<br />
<br />
posTop = min posA posB<br />
posBot = max posA posB<br />
<br />
-- d == a ++ b@([Joker] ++ _ ++ [Joker]) ++ c<br />
<br />
a = take posTop d<br />
x = drop posTop d<br />
b = take (posBot - posTop + 1) x<br />
c = drop (posBot - posTop + 1) x<br />
<br />
-- triple cut<br />
<br />
countCut :: Deck -> Deck<br />
countCut d = lower ++ upper ++ [c]<br />
where<br />
c = last d<br />
(upper, lower) = splitAt (fromEnum c) (init d)<br />
<br />
-- extract the next stream symbol<br />
<br />
findSymbol :: Deck -> Card<br />
findSymbol d = d !! (fromEnum (head d))<br />
<br />
streamStep :: STRef s Deck -> ST s Char<br />
streamStep ref = do<br />
d <- readSTRef ref<br />
let d' = countCut . tripleCut . moveB . moveA $ d<br />
writeSTRef ref d'<br />
let s = findSymbol d'<br />
if isJoker s<br />
then streamStep ref<br />
else return $ cardToLetter s<br />
<br />
streamStart :: ST s (STRef s Deck)<br />
streamStart = newSTRef deck<br />
<br />
stream :: Integer -> Int -> String<br />
stream key len = runST (do<br />
ref <- streamStart<br />
d <- readSTRef ref<br />
writeSTRef ref $ keyDeck key d<br />
sequence . replicate len $ streamStep ref)<br />
<br />
testStream = stream 0 10 == "DWJXHYRFDG"<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- the algorithm frame<br />
<br />
-- and this is where i got bored... (-:<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- keying the deck<br />
<br />
keyDeck :: Integer -> Deck -> Deck<br />
keyDeck _ d = d -- (not yet)<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- testing<br />
<br />
test1 = "CLEPK HHNIY CFPWH FDFEH"<br />
test2 = "ABVAW LWZSY OORYK DUPVH"<br />
</pre></div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher/Solution_Matthias&diff=7316Haskell Quiz/The Solitaire Cipher/Solution Matthias2006-10-26T07:16:24Z<p>Fis: </p>
<hr />
<div><pre><br />
module Main where<br />
import Maybe<br />
import Monad<br />
import Char<br />
import List<br />
import Control.Exception<br />
import Control.Monad.ST<br />
import Data.STRef<br />
<br />
{-<br />
<br />
carelessly written. i haven't looked much at the discussion or at the other solutions, so there is certainly room for improvent, cleanup, and completion.<br />
<br />
-}<br />
<br />
----------------------------------------------------------------------<br />
-- the deck<br />
<br />
data Suit = Clubs | Diamonds | Hearts | Spades<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Suit where<br />
toEnum 0 = Clubs<br />
toEnum 1 = Diamonds<br />
toEnum 2 = Hearts<br />
toEnum 3 = Spades<br />
toEnum i = error ("enum Suit: " ++ show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 3]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 3]<br />
<br />
fromEnum Clubs = 0<br />
fromEnum Diamonds = 1<br />
fromEnum Hearts = 2<br />
fromEnum Spades = 3<br />
<br />
data Base = Ace | Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Base where<br />
toEnum 1 = Ace<br />
toEnum 2 = Two<br />
toEnum 3 = Three<br />
toEnum 4 = Four<br />
toEnum 5 = Five<br />
toEnum 6 = Six<br />
toEnum 7 = Seven<br />
toEnum 8 = Eight<br />
toEnum 9 = Nine<br />
toEnum 10 = Ten<br />
toEnum 11 = Jack<br />
toEnum 12 = Queen<br />
toEnum 13 = King<br />
toEnum i = error ("enum Base: " ++ show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 13]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 13]<br />
<br />
fromEnum Ace = 1<br />
fromEnum Two = 2<br />
fromEnum Three = 3<br />
fromEnum Four = 4<br />
fromEnum Five = 5<br />
fromEnum Six = 6<br />
fromEnum Seven = 7<br />
fromEnum Eight = 8<br />
fromEnum Nine = 9<br />
fromEnum Ten = 10<br />
fromEnum Jack = 11<br />
fromEnum Queen = 12<br />
fromEnum King = 13<br />
<br />
data Card = Card Base Suit | JokerA | JokerB<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
instance Enum Card where<br />
fromEnum JokerA = 53<br />
fromEnum JokerB = 53<br />
fromEnum (Card base suit) = fromEnum base + (fromEnum suit * 13)<br />
<br />
toEnum 53 = error "Jokers break instance Enum Card."<br />
toEnum i | i >= 1 && i <= 52 = Card (toEnum ((i - 1) `mod` 13 + 1)) (toEnum ((i - 1) `div` 13))<br />
toEnum i = error (show i)<br />
<br />
enumFrom x = map toEnum [fromEnum x .. 52] ++ [JokerA, JokerB]<br />
enumFromThen x y = map toEnum [fromEnum x, fromEnum y .. 52] ++ [JokerA, JokerB]<br />
<br />
isJoker :: Card -> Bool<br />
isJoker = (`elem` [JokerA, JokerB])<br />
<br />
type Deck = [Card]<br />
<br />
isDeck d = sort d == deck<br />
<br />
deck :: [Card]<br />
deck = [Card Ace Clubs ..]<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- a few auxiliary transformations<br />
<br />
cardToLetter :: Card -> Char<br />
cardToLetter JokerA = error "cardToLetter: please don't convert jokers to letters."<br />
cardToLetter JokerB = error "cardToLetter: please don't convert jokers to letters."<br />
cardToLetter c = chr ((fromEnum c - 1) `mod` 26 + ord 'A')<br />
<br />
letterToCard :: Char -> Card<br />
letterToCard c<br />
| c <= 'A' || c >= 'Z' = error "letterToCard: only capitals [A-Z] can be converted into cards."<br />
| otherwise = toEnum (ord c - ord 'A' + 1)<br />
<br />
cleanupInput :: String -> [String]<br />
cleanupInput = groupN 5 'X' . catMaybes . map f<br />
where<br />
f c | ord c >= ord 'A' && ord c <= ord 'Z' = Just c<br />
| ord c >= ord 'a' && ord c <= ord 'z' = Just $ toUpper c<br />
| otherwise = Nothing<br />
<br />
groupN :: Int -> a -> [a] -> [[a]]<br />
groupN n pad = f n<br />
where<br />
f 0 xs = [] : f n xs<br />
f i (x:xs) = let (l:ls) = f (i-1) xs in (x:l):ls<br />
f i [] = if i < n then [replicate i pad] else []<br />
<br />
intersperseNth :: Int -> a -> [a] -> [a] -- we don't need that any more now, but it's still a cool funktion. (:<br />
intersperseNth n c = f n<br />
where<br />
f 0 xs = c : f n xs<br />
f i (x:xs) = x : f (i-1) xs<br />
f _ [] = []<br />
<br />
newXOR :: Char -> Card -> Char<br />
newXOR c o<br />
| c <= 'A' || c >= 'Z' = error ("newXOR: illegal character: " ++ show c)<br />
| isJoker o = error ("newXOR: illegal card: " ++ show o)<br />
| otherwise = let<br />
c' = ord c - ord 'A'<br />
o' = fromEnum o - 1<br />
in chr ((c' + o') `mod` 26 + 1)<br />
<br />
-- (It may also be interesting to write an instance of Num for Card, but let's see how far we get without one first...)<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- the stream<br />
<br />
-- circular moves: think of the deck as being a ring, not a list, and always move JokerA one card down, and JokerB two.<br />
<br />
moveA :: Deck -> Deck<br />
moveA = f []<br />
where<br />
f acc (JokerA : x : xs) = reverse acc ++ (x : JokerA : xs)<br />
f acc (JokerA : []) = last acc : JokerA : tail (reverse acc)<br />
f acc (x : xs) = f (x : acc) xs<br />
<br />
moveB :: Deck -> Deck<br />
moveB = f []<br />
where<br />
f acc (JokerB : x : y : ys) = reverse acc ++ (x : y : JokerB : ys)<br />
f acc (JokerB : x : []) = last acc : JokerB : tail (reverse (x : acc))<br />
f acc (JokerB : []) = case reverse acc of (a : b : ccc) -> a : b : JokerB : ccc<br />
f acc (x : xs) = f (x : acc) xs<br />
<br />
-- first triple cut: split at jokers and shuffle triples<br />
<br />
tripleCut :: Deck -> Deck<br />
tripleCut d = c ++ b ++ a<br />
where<br />
posA = fromJust $ findIndex (== JokerA) d<br />
posB = fromJust $ findIndex (== JokerB) d<br />
<br />
posTop = min posA posB<br />
posBot = max posA posB<br />
<br />
-- d == a ++ b@([Joker] ++ _ ++ [Joker]) ++ c<br />
<br />
a = take posTop d<br />
x = drop posTop d<br />
b = take (posBot - posTop + 1) x<br />
c = drop (posBot - posTop + 1) x<br />
<br />
-- triple cut<br />
<br />
countCut :: Deck -> Deck<br />
countCut d = lower ++ upper ++ [c]<br />
where<br />
c = last d<br />
(upper, lower) = splitAt (fromEnum c) (init d)<br />
<br />
-- extract the next stream symbol<br />
<br />
findSymbol :: Deck -> Card<br />
findSymbol d = d !! (fromEnum (head d))<br />
<br />
streamStep :: STRef s Deck -> ST s Char<br />
streamStep ref = do<br />
d <- readSTRef ref<br />
let d' = countCut . tripleCut . moveB . moveA $ d<br />
writeSTRef ref d'<br />
let s = findSymbol d'<br />
if isJoker s<br />
then streamStep ref<br />
else return $ cardToLetter s<br />
<br />
streamStart :: ST s (STRef s Deck)<br />
streamStart = newSTRef deck<br />
<br />
stream :: Integer -> Int -> String<br />
stream key len = runST (do<br />
ref <- streamStart<br />
d <- readSTRef ref<br />
writeSTRef ref $ keyDeck key d<br />
sequence . replicate len $ streamStep ref)<br />
<br />
testStream = stream 0 10 == "DWJXHYRFDG"<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- the algorithm frame<br />
<br />
-- and this is where i got bored... (-:<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- keying the deck<br />
<br />
keyDeck :: Integer -> Deck -> Deck<br />
keyDeck _ d = d -- (not yet)<br />
<br />
<br />
----------------------------------------------------------------------<br />
-- testing<br />
<br />
test1 = "CLEPK HHNIY CFPWH FDFEH"<br />
test2 = "ABVAW LWZSY OORYK DUPVH"<br />
</pre></div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher&diff=7315Haskell Quiz/The Solitaire Cipher2006-10-26T07:11:01Z<p>Fis: </p>
<hr />
<div>The first puzzle of the rubyquizz series was to implement the Solitaire cipher [http://en.wikipedia.org/wiki/Solitaire_(cipher)] Bruce Schneier made for Neil Stephenson's Cryptonomicon [http://en.wikipedia.org/wiki/Cryptonomicon]. The twist is that it's designed to be done by a Spy in a containment camp with no other tools than a deck of bridge cards.<br />
<br />
<b>The problem:</b><br />
<br />
* http://www.rubyquiz.com/quiz1.html<br />
* http://www.schneier.com/solitaire.html<br />
<br />
<b>Solutions:</b><br />
<br />
* [[Haskell Quiz/The Solitaire Cipher/Solution Don|Don]]<br />
* [[Haskell Quiz/The Solitaire Cipher/Solution Matthias|Matthias]]</div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher&diff=7313Haskell Quiz/The Solitaire Cipher2006-10-26T07:08:03Z<p>Fis: </p>
<hr />
<div>The first puzzle of the rubyquizz series was to implement the Solitaire cipher [http://en.wikipedia.org/wiki/Solitaire_(cipher)] Bruce Schneier made for Neil Stephenson's Cryptonomicon [http://en.wikipedia.org/wiki/Cryptonomicon]. The twist is that it's designed to be done by a Spy in a containment camp with no other tools than a deck of bridge cards.<br />
<br />
<b>The problem:</b><br />
<br />
* http://www.rubyquiz.com/quiz1.html<br />
* http://www.schneier.com/solitaire.html<br />
<br />
<b>Solutions:</b><br />
<br />
* [[Haskell Quiz/The Solitaire Cipher/Solution Don|Don]]</div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher&diff=7312Haskell Quiz/The Solitaire Cipher2006-10-26T07:06:37Z<p>Fis: </p>
<hr />
<div>The first puzzle of the rubyquizz series was to implement the Solitaire cipher [http://en.wikipedia.org/wiki/Solitaire_(cipher)] Bruce Schneier made for Neil Stephenson's Cryptonomicon [http://en.wikipedia.org/wiki/Cryptonomicon]. The twist is that it's designed to be done by a Spy in a containment camp with no other tools than a deck of bridge cards.<br />
<br />
<b>The problem:</b><br />
<br />
* http://www.rubyquiz.com/quiz1.html<br />
<br />
<b>Solutions:</b><br />
<br />
* [[Haskell Quiz/The Solitaire Cipher/Solution Don|Don]]</div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher/Solution_Dolio&diff=7310Haskell Quiz/The Solitaire Cipher/Solution Dolio2006-10-26T06:57:38Z<p>Fis: Haskell Quiz/The Solitaire Cipher moved to Haskell Quiz/The Solitaire Cipher/Solution Don</p>
<hr />
<div><haskell><br />
module Main where<br />
import Data.List<br />
import Data.Char<br />
import Data.Ix<br />
import Control.Monad<br />
import Control.Monad.State<br />
import System<br />
import System.Random<br />
<br />
data Card = A | B | C Int deriving (Eq, Show)<br />
type Deck = [Card]<br />
type Cipher a = State Deck a<br />
<br />
unkeyed = map C [1..52] ++ [A,B]<br />
<br />
isJoker c = c == A || c == B<br />
<br />
value (C i) = i<br />
value _ = 53<br />
<br />
-- en/decodes upper case characters into a 0 - 25 Int representation<br />
-- (for easier arithmetic than 1 - 26)<br />
decode n = chr (n + 65)<br />
encode n = ord n - 65<br />
<br />
-- Shuffles a given deck using n as the seed for the random generator<br />
shuffle n = map snd . sortBy (comparing fst) . zip (randoms $ mkStdGen n :: [Int])<br />
where comparing f a b = compare (f a) (f b)<br />
<br />
-- Scrubs/pads a string to turn it into the format expected by the cipher<br />
scrub = break5 . pad . filter isAlpha . map toUpper<br />
where<br />
pad l = l ++ replicate ((5 - length l) `mod` 5) 'X'<br />
break5 l <br />
| null t = h<br />
| otherwise = h ++ " " ++ break5 t<br />
where (h, t) = splitAt 5 l<br />
<br />
-- Moves element e in l forward n places using the appropriate rules<br />
push n e l = t ++ [e] ++ b<br />
where<br />
(Just i) = elemIndex e l<br />
l' = delete e l<br />
i' = if i + n >= length l then 1 + i + n else i + n<br />
(t,b) = splitAt (i' `mod` (length l)) l'<br />
<br />
-- Performs the triple cut<br />
tcut l = bottom ++ middle ++ top<br />
where<br />
[i,j] = findIndices isJoker l<br />
(top, m) = splitAt i l<br />
(middle, bottom) = splitAt (1 + j - i) m<br />
<br />
-- Performs the counting cut<br />
ccut l = init bottom ++ top ++ [last bottom]<br />
where<br />
n = value (last l)<br />
(top, bottom) = splitAt n l<br />
<br />
-- Extracts a code from a given deck according to the appropriate rules.<br />
-- Returns Nothing in the event that a joker is picked<br />
extract l@(h:_) = if isJoker c then Nothing else Just (value c)<br />
where<br />
n = value h<br />
c = l !! n<br />
<br />
-- Gets the next code in the key stream<br />
getCode = do modify (ccut . tcut . push 2 B . push 1 A)<br />
deck <- get<br />
maybe getCode return (extract deck)<br />
<br />
-- Uses the function f and initial deck d to en/decrypt a message<br />
crypt f d = map decode . flip evalState d . mapM cipher . map encode<br />
where<br />
cipher a <br />
| inRange (0,25) a = getCode >>= return . flip mod 26 . f a<br />
| otherwise = return a<br />
<br />
decrypt = crypt (-)<br />
encrypt = crypt (+)<br />
<br />
crypto f = unlines . map f . map scrub . lines<br />
<br />
main = do (o:l) <- getArgs<br />
let deck = if null l then unkeyed else shuffle (read (head l)) unkeyed<br />
case o of<br />
"d" -> interact (crypto $ decrypt deck)<br />
"e" -> interact (crypto $ encrypt deck)<br />
_ -> putStrLn "Unrecognized option."<br />
</haskell></div>Fishttps://wiki.haskell.org/index.php?title=Haskell_Quiz/The_Solitaire_Cipher&diff=7311Haskell Quiz/The Solitaire Cipher2006-10-26T06:57:38Z<p>Fis: Haskell Quiz/The Solitaire Cipher moved to Haskell Quiz/The Solitaire Cipher/Solution Don: extended page hierarchy to make room for multiple solutions and discussion for each puzzle</p>
<hr />
<div>#redirect [[Haskell Quiz/The Solitaire Cipher/Solution Don]]</div>Fishttps://wiki.haskell.org/index.php?title=Books&diff=6538Books2006-10-06T09:19:06Z<p>Fis: </p>
<hr />
<div>Books and tutorials covering many aspects of Haskell.<br />
<br />
=Language and library definition=<br />
<br />
<DL><br />
<DT>Simon Peyton Jones: [http://titles.cambridge.org/catalogue.asp?isbn=0521826144 <EM>Haskell 98 Language and Libraries</EM>], Cambridge University Press, 2003, Hardback, 272 pages, ISBN: 0521826144, £35.00<br />
<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
Haskell is the world's leading lazy functional programming language,<br />
widely used for teaching, research, and applications. The language<br />
continues to develop rapidly, but in 1998 the community decided to<br />
capture a stable snapshot of the language: Haskell 98. All Haskell<br />
compilers support Haskell 98, so practitioners and educators alike<br />
have a stable base for their work. This book constitutes the agreed<br />
definition of the Haskell 98, both the language itself and its<br />
supporting libraries. It has been considerably revised and refined<br />
since the original definition, and appears in print for the first<br />
time. It should be a standard reference work for anyone involved in<br />
research, teaching, or application of Haskell.<br />
</BLOCKQUOTE> <br />
The entire language definition is also available online:<br />
[[Language_and_library_specification|Language and library specification]]<br />
</DT><br />
</DL><br />
<br />
= Textbooks=<br />
<br />
<DL><br />
<DT>Paul Hudak: [http://www.haskell.org/soe <EM>The Haskell School of Expression: Learning Functional Programming through Multimedia</EM>], Cambridge University Press, New York, 2000, 416<br />
pp, 15 line diagrams, 75 exercises, Paperback $29.95, ISBN:<br />
0521644089, Hardback $74.95, ISBN: 0521643384<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
This book teaches functional programming as a way of thinking and<br />
problem solving, using Haskell, the most popular purely functional<br />
language. Rather than using the conventional mathematical examples<br />
commonly found in other programming language textbooks, the author<br />
draws examples from multimedia applications, including graphics,<br />
animation, and computer music, thus rewarding the reader with working<br />
programs for inherently more interesting applications. Aimed at both<br />
beginning and advanced programmers, this tutorial begins with a gentle<br />
introduction to functional programming and moves rapidly on to more<br />
advanced topics. An underlying theme is the design and implementation<br />
of domain specific languages, using three examples: FAL (a Functional<br />
Animation Language), IRL (an Imperative Robot Language), and MDL (a<br />
Music Description Language). Details about programming in Haskell<br />
are presented in boxes throughout the text so they can be easily<br />
referred to and found quickly.<br />
<br />
The book's Web Site contains source files for all programs in the<br />
text, as well as the graphics libraries to run them under Windows and<br />
Linux platforms. It also contains PowerPoint slides useful for<br />
teaching a course using the textbook.<br />
</blockquote><br />
<DT>Simon Thompson: [http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e/ <EM>Haskell: The Craft of Functional Programming</EM>], Second Edition,<br />
Addison-Wesley, 507&nbsp;pages, paperback, 1999. ISBN<br />
0-201-34275-8.<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
The second edition of Haskell: The Craft of Functional Programming is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on the process of crafting programs and the text contains many examples and running case studies, as well as advice an program design, testing, problem solving and how to avoid common pitfalls. <br />
<br />
Building on the strengths of the first edition, the book includes many new and improved features: <br />
*Complete coverage of Haskell 98, the standard version of Haskell which will be stable and supported by implementations for years to come. <br />
*An emphasis on software engineering principles, encouraging a disciplined approach to building reusable libraries of software components. <br />
*Detailed coverage of the Hugs interpreter with an appendix covering other implementations. <br />
*A running case study of pictures emphasizes the built-in functions which appear in the standard prelude and libraries. It is also used to give an early preview of some of the more complex language features, such as high-order functions. <br />
*List comprehensions and the standard functions over lists are covered before recursion. <br />
*Early coverage of polymorphism supporting the "toolkit" approach and encouraging the resuse of built-in functions and types. <br />
*Extensive reference material containing details of further reading in books, journals and on the World Wide Web. <br />
*Accompanying Web Site supporting the book, containing all the program code, further teaching materials and other useful resources. <br />
<B>Synopsis</B><BR> <br />
This books introduces Haskell at a level appropriate for those with little or no prior experience of functional programming. The emphasis is on the process of crafting programs, solving problems, and avoiding common errors.<br />
</blockquote><br />
<br />
<DT>Richard Bird: [http://www.prenhall.com/allbooks/ptr_0134843460.html <EM>Introduction to Functional Programming using Haskell</EM>], 2nd edition, Prentice Hall Press, 1998, 460 pp., ISBN: 0-13-484346-0.<br />
<blockquote><br />
From the cover:<br />
<br />
After the success of the first edition, Introduction to Functional Programming using Haskell has been thoroughly updated and revised to provide a complete grounding in the principles and techniques of programming with functions.<br />
<br />
The second edition uses the popular language Haskell to express functional programs. There are new chapters on program optimisation, abstract datatypes in a functional setting, and programming in a monadic style. There are completely new case studies, and many new exercises.<br />
<br />
As in the first edition, there is an emphasis on the fundamental techniques for reasoning about functional programs, and for deriving them systematically from their specifications.<br />
<br />
The book is self-contained, assuming no prior knowledge of programming, and is suitable as an introductory undergraduate text for first- or second-year students.<br />
</blockquote><br />
<br />
<DT>Antony Davie: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521277248 <EM>An Introduction to Functional Programming Systems Using Haskell</EM>], Cambridge University Press, 1992. ISBN 0-521-25830-8 (hardback). ISBN 0-521-27724-8 (paperback).<br />
<blockquote><br />
Cover:<br />
<br />
Functional programming is a style of programming that has become increasingly popular during the past few years.<br />
Applicative programs have the advantage of being almost immediately expressible as functional descriptions; they can<br />
be proved correct and transformed through the referential transparency property.<br />
<br />
This book presents the basic concepts of functional programming, using the language Haskell for examples. The author<br />
incorporates a discussion of lambda calculus and its relationship with Haskell, exploring the implications for<br />
raparallelism. Contents: SASL for Beginners / Examples of SASL Programming / More Advanced Applicative Programming<br />
Techniques / Lambda Calculus / The Relationship Between Lambda Calculus and SASL / Program Transformation and<br />
Efficiency / Correctness, Equivalence and Program Verification / Landin's SECD Machine and Related<br />
Implementations / Further Implementation Techniques / Special Purpose Hardware / The Applicative Style of<br />
Semantics / Other Applicative Languages / Implications for Parallelism / Functional Programming in Von Neumann<br />
Languages <br />
</blockquote><br />
<br />
<DT>Fethi Rabhi and Guy Lapalme: [http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html <EM> Algorithms: A functional programming approach</EM>], <br />
Addison-Wesley, 235&nbsp;pages, paperback, 1999. ISBN<br />
0-201-59604-0<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
The authors challenge more traditional methods of teaching algorithms<br />
by using a functional programming context, with Haskell as an<br />
implementation language. This leads to smaller, clearer and more<br />
elegant programs which enable the programmer to understand the<br />
algorithm more quickly and to use that understanding to explore<br />
alternative solutions. <br><br />
<b>Key features:</b><br />
*Most chapters are self-contained and can be taught independently from each other.<br />
*All programs are in Haskell'98 and provided on a WWW site.<br />
*End of chapter exercises throughout.<br />
*Comprehensive index and bibliographical notes.<br />
<B>Synopsis</B><BR> <br />
The book is organised as a classic algorithms book according to topics<br />
such as Abstract Data Types, sorting and searching. It uses a<br />
succession of practical programming examples to develop in the reader<br />
problem-solving skills which can be easily transferred to other<br />
language paradigms. It also introduces the idea of capturing<br />
algorithmic design strategies (e.g. Divide-and-Conquer, Dynamic<br />
Programming) through higher-order functions.<br><br />
<b>Target audience</b><br><br />
The book is intended for computer science students taking algorithms<br />
and/or (basic or advanced) functional programming courses.<br />
</BLOCKQUOTE><br />
<br />
<dt>Jeremy Gibbons and Oege de Moor (eds.): [http://www.palgrave.com/catalogue/catalogue.asp?Title_Id=0333992857 <em>The Fun of Programming</em>],Palgrave, 2002, 288 pages. ISBN 0333992857.<br />
<blockquote><br />
<b>Book description:</b><br><br />
In this textbook, leading researchers give tutorial expositions on the current state of the art of functional<br />
programming. The text is suitable for an undergraduate course immediately following an introduction to<br />
functional programming, and also for self-study. All new concepts are illustrated by plentiful examples,<br />
as well as exercises. A website gives access to accompanying software.<br />
</blockquote><br />
<br />
<dt> Cordelia Hall and John O'Donnell: [http://www.dcs.gla.ac.uk/~jtod/discrete-mathematics/ <em>Discrete Mathematics Using a Computer</em>],<br />
Springer, 2000, 360 pages. ISBN 1-85233-089-9.<br />
<blockquote><br />
<b>Book description:</b><br><br />
This book introduces the main topics of discrete mathematics with a strong emphasis on<br />
applications to computer science. It uses computer programs to implement and illustrate<br />
the mathematical ideas, helping the reader to gain a concrete understanding of the<br />
abstract mathematics. The programs are also useful for practical calculations, and they<br />
can serve as a foundation for larger software packages. <br />
<br />
Designed for first and second year undergraduate students, the book is also ideally suited<br />
to self-study. No prior knowledge of functional programming is required; the book and<br />
the online documentation provide everything you will need. <br />
</blockquote><br />
<br />
<dt>Kees Doets and Jan van Eijck: [http://www.cwi.nl/~jve/HR <em>The Haskell Road to Logic, Maths and Programming</em>]. King's College Publications, London, 2004. ISBN 0-9543006-9-6 (14.00 pounds, $25.00).<br />
<blockquote><br />
<b>Book description:</b><br><br />
The purpose of this book is to teach logic and mathematical reasoning<br />
in practice, and to connect logical reasoning with computer<br />
programming. Throughout the text, abstract concepts are linked to<br />
concrete representations in Haskell. Everything one has to know about<br />
programming in Haskell to understand the examples in the book is<br />
explained as we go along, but we do not cover every aspect of the<br />
language. Haskell is a marvelous demonstration tool for logic and<br />
maths because its functional character allows implementations to<br />
remain very close to the concepts that get implemented, while the<br />
laziness permits smooth handling of infinite data structures.<br />
<br />
We do not assume that our readers have previous experience with either<br />
programming or construction of formal proofs. We do assume previous<br />
acquaintance with mathematical notation, at the level of secondary<br />
school mathematics. Wherever necessary, we will recall relevant <br />
facts. Everything one needs to know about mathematical<br />
reasoning or programming is explained as we go along. We do assume<br />
that our readers are able to retrieve software from the Internet and<br />
install it, and that they know how to use an editor for constructing<br />
program texts.<br />
<br />
After having worked through the material in the book, i.e., after<br />
having digested the text and having carried out a substantial number<br />
of the exercises, the reader will be able to write interesting<br />
programs, reason about their correctness, and document them in a clear<br />
fashion. The reader will also have learned how to set up mathematical<br />
proofs in a structured way, and how to read and digest mathematical<br />
proofs written by others.<br />
<br />
The book can be used as a course textbook, but since it comes with<br />
solutions to all exercises (electronically available from the authors<br />
upon request) it is also well suited for private study. The source<br />
code of all programs discussed in the text, a list of errata, <br />
further relevant material and an email link to the authors<br />
can be found [http://www.cwi.nl/~jve/HR here].<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones: <em>Implementation of Functional Programming Language</em>,Prentice-Hall, 1987. ISBN 0134533259.<br />
<br />
<dt>Simon Peyton Jones, David Lester: <em>Implementing Functional Languages</em>, 1992.<br><br />
<blockquote><br />
The book is out of print. The full sources and a postscript version are <br />
[http://research.microsoft.com/Users/simonpj/Papers/papers.html available for free].<br />
</blockquote><br />
<br />
<dt>Simon Thompson: <em>Type Theory and Functional Programming</em>, Addison-Wesley, 1991. ISBN 0-201-41667-0.<br />
<blockquote><br />
Now out of print, the original version is available [http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ here].<br />
<br />
<em>Preface</em>:<br />
Constructive Type theory has been a topic of research interest to computer scientists,<br />
mathematicians, logicians and philosophers for a number of years. For computer scientists it provides<br />
a framework which brings together logic and programming languages in a most elegant and fertile way:<br />
program development and verification can proceed within a single system. Viewed in a different way,<br />
type theory is a functional programming language with some novel features, such as the totality of<br />
all its functions, its expressive type system allowing functions whose result type depends upon the<br />
value of its input, and sophisticated modules and abstract types whose interfaces can contain logical<br />
assertions as well as signature information. A third point of view emphasizes that programs (or<br />
functions) can be extracted from proofs in the logic.<br />
</blockquote><br />
<br />
</DL><br />
<br />
=Tutorials=<br />
<br />
==Introductions to Haskell==<br />
<br />
;[http://www.haskell.org/tutorial/ A Gentle Introduction to Haskell] <br />
:By Paul Hudak, John Peterson, and Joseph H. Fasel. The title is a bit misleading. Some knowledge of another functional programming language is expected. The emphasis is on the type system and those features which are really new in Haskell (compared to other functional programming languages). A classic.<br />
<br />
;[http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf Yet Another Haskell Tutorial]<br />
:By Hal Daume III et al. A recommended tutorial for Haskell that is still under construction but covers already much ground. Also a classic text.<br />
<br />
;[http://www.haskell.org/~pairwise/intro/intro.html Haskell Tutorial for C Programmers]<br />
:By Eric Etheridge. From the intro: "This tutorial assumes that the reader is familiar with C/C++, Python, Java, or Pascal. I am writing for you because it seems that no other tutorial was written to help students overcome the difficulty of moving from C/C++, Java, and the like to Haskell."<br />
<br />
;[http://www-106.ibm.com/developerworks/edu/os-dw-linuxhask-i.html Beginning Haskell] <br />
:From IBM developerWorks. This tutorial targets programmers of imperative languages wanting to learn about functional programming in the language Haskell. If you have programmed in languages such as C, Pascal, Fortran, C++, Java, Cobol, Ada, Perl, TCL, REXX, JavaScript, Visual Basic, or many others, you have been using an imperative paradigm. This tutorial provides a gentle introduction to the paradigm of functional programming, with specific illustrations in the Haskell 98 language. (Free registration required.)<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/teaching/Hskurs_toc.html Online Haskell Course] <br />
:By Ralf Hinze (in German).<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/tutorials.html Tutorial Papers in Functional Programming].<br />
:A collection of links to other Haskell tutorials, from John Hughes.<br />
<br />
;[http://www.cs.ou.edu/cs1323h/textbook/haskell.shtml Two Dozen Short Lessons in Haskell] <br />
:By Rex Page. A draft of a textbook on functional programming, available by ftp. It calls for active participation from readers by omitting material at certain points and asking the reader to attempt to fill in the missing information based on knowledge they have already acquired. The missing information is then supplied on the reverse side of the page. <br />
<br />
;[http://pleac.sourceforge.net/pleac_haskell/t1.html PLEAC-Haskell]<br />
:Following the Perl Cookbook (by Tom Christiansen and Nathan Torkington, published by O'Reilly) spirit, the PLEAC Project aims to gather fans of programming, in order to implement the solutions in other programming languages.<br />
<br />
;[ftp://ftp.geoinfo.tuwien.ac.at/navratil/HaskellTutorial.pdf Haskell-Tutorial] <br />
:By Damir Medak and Gerhard Navratil. The fundamentals of functional languages for beginners. <br />
<br />
;[http://en.wikibooks.org/wiki/Haskell Programming Haskell Wikibook] <br />
:A communal effort by several authors to produce the definitive Haskell textbook. Its very much a work in progress at the moment, and contributions are welcome.<br />
<br />
;[http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung Video Lectures] <br />
:Lectures (in English) by Jürgen Giesl. About 30 hours in total, and great for learning Haskell. The lectures are 2005-SS-FP.V01 through 2005-SS-FP.V26. Videos 2005-SS-FP.U01 through 2005-SS-FP.U11 are exercise answer sessions, so you probably don't want those.<br />
<br />
;[http://www.cs.utoronto.ca/~trebla/fp/ Albert's Functional Programming Course] <br />
:A 15 lesson introduction to most aspects of Haskell.<br />
<br />
;[http://www.iceteks.com/articles.php/haskell/1 Introduction to Haskell]<br />
:By Chris Dutton, An "attempt to bring the ideas of functional programming to the masses here, and an experiment in finding ways to make it easy and interesting to follow".<br />
<br />
;[http://www.csc.depauw.edu/~bhoward/courses/0203Spring/csc122/haskintro/ An Introduction to Haskell]<br />
:A brief introduction, by Brian Howard.<br />
<br />
;[http://web.syntaxpolice.org/lectures/haskellTalk/slides/index.html Introduction to Haskell]<br />
:By Isaac Jones (2003).<br />
<br />
;[http://www.linuxjournal.com/article/9096 Translating Haskell into English]<br />
:By Shannon Behrens, a glimpse of the Zen of Haskell, without requiring that they already be Haskell converts.<br />
<br />
;[http://www.thaiopensource.com/relaxng/derivative.html An algorithm for RELAX NG validation]<br />
:by James Clark (of RELAX NG fame). Describes an algorithm for validating an XML document against a RELAX NG schema, uses Haskell to describe the algorithm. The algorithm in Haskell and Java is then [http://www.donhopkins.com/drupal/node/117 discussed here].<br />
<br />
===Real world tutorials===<br />
<br />
These tutorials examine using Haskell to writing complex real-wrold applications<br />
<br />
;[[Hitchhikers Guide to the Haskell]]<br />
: Tutorial for C/Java/OCaml/... programers by Dmitry Astapov. From the intro: "This text intends to introduce the reader to the practical aspects of Haskell from the very beginning (plans for the first chapters include: I/O, darcs, Parsec, QuickCheck, profiling and debugging, to mention a few)".<br />
<br />
;[http://haskell.org/haskellwiki/IO_inside Haskell I/O inside: Down the Rabbit's Hole]<br />
:By Bulat Ziganshin (2006), a comprehensive tutorial on using IO monad.<br />
<br />
;[http://research.microsoft.com/%7Esimonpj/Papers/marktoberdorf Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell]<br />
:Simon Peyton Jones. Presented at the 2000 Marktoberdorf Summer School. In "Engineering theories of software construction", ed Tony Hoare, Manfred Broy, Ralf Steinbruggen, IOS Press, ISBN 1 58603 1724, 2001, pp47-96. The standard reference for monadic IO in GHC/Haskell. <br><strong>Abstract:</strong>Functional programming may be beautiful, but to write real applications we must grapple with awkward real-world issues: input/output, robustness, concurrency, and interfacing to programs written in other languages.<br />
<br />
;[http://www.reid-consulting-uk.ltd.uk/docs/ffi.html A Guide to Haskell's Foreign Function Interface]<br />
:A guide to using the foreign function interface extension, using the rich set of functions in the Foreign libraries, design issues, and FFI preprocessors.<br />
<br />
===Older tutorials===<br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/manuals/haskeller.dvi.gz The Little Haskeller] <br />
:By Cordelia Hall and John Hughes. 9. November 1993, 26 pages. An introduction using the Chalmers Haskell B interpreter (hbi). Beware that it relies very much on the user interface of hbi which is quite different for other Haskell systems, and the tutorials cover Haskell 1.2 , not Haskell 98.<br />
<br />
;[http://www.cs.uu.nl/people/jeroen/courses/fp-eng.pdf Functional Programming]<br />
:By Jeroen Fokker, 1995. (153 pages, 600 KB). Textbook for learning functional programming with Gofer (an older implementation of Haskell). Here without Chapters&nbsp;6 and&nbsp;7.<br />
<br />
;[http://wiki.python.org/moin/PythonVsHaskell Comparing Haskell and Python]<br />
:A short overview of similarities and differences between Haskell and Python.<br />
<br />
==Reference material==<br />
<br />
;[http://undergraduate.csse.uwa.edu.au/units/230.301/lectureNotes/tourofprelude.html A Tour of the Haskell Prelude (basic functions)] <br />
:By Bernie Pope and Arjan van IJzendoorn.<br />
<br />
;[http://cs.anu.edu.au/Student/comp1100/haskell/tourofsyntax.html Tour of the Haskell Syntax] <br />
:By Arjan van IJzendoorn.<br />
<br />
;[http://zvon.org/other/haskell/Outputglobal/index.html Haskell Reference] <br />
:By Miloslav Nic.<br />
<br />
;[http://members.chello.nl/hjgtuyl/tourdemonad.html A tour of the Haskell Monad functions]<br />
:By Henk-Jan van Tuyl.<br />
<br />
;[http://www.cse.unsw.edu.au/~en1000/haskell/inbuilt.html Useful Haskell functions]<br />
:An explanation for beginners of many Haskell functions that are predefined in the Haskell Prelude.<br />
<br />
;[http://haskell.org/ghc/docs/latest/html/libraries/ Documentation for the standard libraries]<br />
:Complete documentation of the standard Haskell libraries.<br />
<br />
;[http://www.haskell.org/haskellwiki/Category:Idioms Haskell idioms]<br />
:A collection of articles describing some common Haskell idioms. Often quite advanced.<br />
<br />
;[http://www.haskell.org/haskellwiki/Blow_your_mind Useful idioms]<br />
:A collection of short, useful Haskell idioms.<br />
<br />
;[http://www.haskell.org/haskellwiki/Programming_guidelines Programming guidelines]<br />
:Some Haskell programming and style conventions.<br />
<br />
;[http://haskell.org/haskellwiki/Category:Tutorials A growing list of Haskell tutorials on a diverse range of topics]<br />
:Available on this wiki<br />
<br />
== Motivation for using Haskell ==<br />
<br />
;[http://www.md.chalmers.se/~rjmh/Papers/whyfp.html Why Functional Programming Matters] <br />
:By [http://www.md.chalmers.se/~rjmh/ John Hughes], The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 - 107. Also in: David A. Turner (ed.): Research Topics in Functional Programming, Addison-Wesley, 1990, pp. 17 - 42.<BR> Exposes the advantages of functional programming languages. Demonstrates how higher-order functions and lazy evaluation enable new forms of modularization of programs.<br />
<br />
;[[Why Haskell matters]] <br />
:Discussion of the advantages of using Haskell in particular. An excellent article.<br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/224/index.html Higher-order + Polymorphic = Reusable] <br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. Unpublished, May 1997.<BR> <STRONG>Abstract:</STRONG> This paper explores how certain ideas in object oriented languages have their correspondents in functional languages. In particular we look at the analogue of the iterators of the C++ standard template library. We also give an example of the use of constructor classes which feature in Haskell 1.3 and Gofer.<br />
<br />
;[http://www-128.ibm.com/developerworks/java/library/j-cb07186.html Explore functional programming with Haskell]<br />
:Introduction to the benefits of functional programming in Haskell by Bruce Tate.<br />
<br />
==Analysis and design methods==<br />
<br />
See [[Analysis and design]].<br />
<br />
== Teaching Haskell == <br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/208/index.html Where do I begin? A problem solving approach to teaching functional programming]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. In Krzysztof Apt, Pieter Hartel, and Paul Klint, editors, First International Conference on Declarative Programming Languages in Education. Springer-Verlag, September 1997. <br> <STRONG>Abstract:</STRONG> This paper introduces a problem solving method for teaching functional programming, based on Polya's `How To Solve It', an introductory investigation of mathematical method. We first present the language independent version, and then show in particular how it applies to the development of programs in Haskell. The method is illustrated by a sequence of examples and a larger case study. <br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1995/214/index.html Functional programming through the curriculum]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]and Steve Hill. In Pieter H. Hartel and Rinus Plasmeijer, editors, Functional Programming Languages in Education, LNCS 1022, pages 85-102. Springer-Verlag, December 1995. <br> <STRONG>Abstract:</STRONG> This paper discusses our experience in using a functional language in topics across the computer science curriculum. After examining the arguments for taking a functional approach, we look in detail at four case studies from different areas: programming language semantics, machine architectures, graphics and formal languages. <br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/CK02a.html The Risks and Benefits of Teaching Purely Functional Programming in First Year]<br />
:By [http://www.cse.unsw.edu.au/~chak Manuel M. T. Chakravarty] and [http://www.cse.unsw.edu.au/~keller Gabriele Keller]. Journal of Functional Programming 14(1), pp 113-123, 2004. An earlier version of this paper was presented at Functional and Declarative Programming in Education (FDPE02). <br> <strong>Abstract</strong> We argue that teaching purely functional programming as such in freshman courses is detrimental to both the curriculum as well as to promoting the paradigm. Instead, we need to focus on the more general aims of teaching elementary techniques of programming and essential concepts of computing. We support this viewpoint with experience gained during several semesters of teaching large first-year classes (up to 600 students) in Haskell. These classes consisted of computer science students as well as students from other disciplines. We have systematically gathered student feedback by conducting surveys after each semester. This article contributes an approach to the use of modern functional<br />
languages in first year courses and, based on this, advocates the use of functional languages in this setting.<br />
<br />
==Using monads==<br />
<br />
See also the [[Monad]] HaskellWiki page with another list of tutorials (should this redundancy be removed? -- not sure...)<br />
<br />
;[http://www.nomaware.com/monads/html/ All About Monads] <br />
:By Jeff Newbern. This tutorial aims to explain the concept of a monad and its application to functional programming in a way that is easy to understand and useful to beginning and intermediate Haskell programmers. Familiarity with the Haskell language is assumed, but no prior experience with monads is required. <br />
<br />
;[http://db.ewi.utwente.nl/Publications/PaperStore/db-utwente-0000003696.pdf The Haskell Programmer's Guide to the IO Monad - Don't Panic.] <br />
:Stefan Klinger. This report scratches the surface of category theory, an abstract branch of algebra, just deep enough to find the monad structure. It seems well written.<br />
<br />
;[http://www-users.mat.uni.torun.pl/~fly/materialy/fp/haskell-doc/Monads.html What the hell are Monads?] <br />
:By Noel Winstanley. A basic introduction to monads, monadic programming and IO. This introduction is presented by means of examples rather than theory, and assumes a little knowledge of Haskell. <br />
<br />
;[http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm Monads for the Working Haskell Programmer -- a short tutorial]<br />
:By Theodore Norvell. <br />
<br />
;[http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html You Could Have Invented Monads! (And Maybe You Already Have.)]<br />
:A short tutorial on monads, introduced from a pragmatic approach, with less category theory references <br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/monads.html Systematic Design of Monads]<br />
:John Hughes & Magnus Carlsson. Many useful monads can be designed in a systematic way, by successively adding facilities to a trivial monad. The capabilities that can be added in this way include state, exceptions, backtracking, and output. Here we give a brief description of the trivial monad, each kind of extension, and sketches of some interesting operations that each monad supports.<br />
<br />
;[[Meet Bob The Monadic Lover]]<br />
:by Andrea Rossato. A by-the-author-supposed-to-be funny and short introduction to Monads, with code but without any reference to category theory: what monads look like and what they are useful for, from the perspective of a ... lover. (There is also the slightly more serious [[The Monadic Way]] by the same author.)<br />
<br />
;[http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html Monad Transformers Step by Step]<br />
:Martin Grabm&uuml;ller: a small tutorial on using monad transformers. In contrast to others found on the web, it concentrates on using them, not on their implementation.<br />
<br />
See also [[Research papers/Monads and arrows]]<br />
<br />
==Using arrows==<br />
<br />
This topic has an own HaskellWiki page: [[Arrow]].<br />
<br />
;[http://www.haskell.org/arrows/ Arrows: A General Interface to Computation]<br />
:Ross Paterson's page on arrows.<br />
<br />
HaWiki's [http://haskell.org/hawiki/UnderstandingArrows UnderstandingArrows].<br />
<br />
Monad.Reader's [http://www.haskell.org/tmrwiki/ArrowsIntroduction ArrowsIntroduction] article.<br />
<br />
See also [[Research papers/Monads and arrows]]<br />
<br />
== Attribute grammars ==<br />
<br />
This topic has an own HakellWiki page: [[Attribute grammar]]<br />
<br />
== Categorical programming ==<br />
<br />
See its own HaskellWiki page: [[Category theory#Categorical programming]].<br />
<br />
== Data structures ==<br />
<br />
;[http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521663504 Purely Functional Data Structures]<br />
:[http://www.cs.columbia.edu/~cdo/ Chris Okasaki], 232 pp., Cambridge University Press, 1998. ISBN 0-521-63124-6<BR> From the cover: <BLOCKQUOTE> Most books on data structures assume an imperative language like C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures and data structure design techniques from the point of view of functional languages. It includes code for a wide assortment both of classical data structures and of data structures developed exclusively for functional languages.This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study. [http://www.cs.columbia.edu/~cdo/pfds-haskell.tar.gz Haskell source code for the book] </BLOCKQUOTE><br />
<br />
See [[Research papers/Data structures]]<br />
<br />
==Schools on advanced funtional programming==<br />
<br />
<EM>Advanced Functional Programming</EM>, First International Spring<br />
School on Advanced Functional Programming Techniques, Bastad, Sweden, LNCS 925, Springer-Verlag, 1995 (editors: J. Jeuring, E. Meijer).<br />
*<EM>Functional Parsers</EM> by Jeroen Fokker, p.&nbsp;1-23.<br />
*<EM>Monads for functional programming</EM> by Philip Wadler, p.&nbsp;24-52.<br />
*<EM>The Design of a Pretty-printing Library</EM> by John Hughes, p.&nbsp;52-96.<br />
*<EM>Functional Programming with Overloading and Higher-Order Polymorphism</EM>, Mark P. Jones, p.&nbsp;97-136.<br />
*<EM>Programming with Fudgets</EM> by Thomas Hallgren and Magnus Carlsson, p.&nbsp;137-182.<br />
*<EM>Constructing Medium Sized Efficient Functional Programs in Clean</EM> by Marko C.J.D. van Eekelen and Rinus J. Plasmeijer, p.&nbsp;183-227.<br />
*<EM>Merging Monads and Folds for Functional Programming</EM> by Erik Meijer and Johan Jeuring, p.&nbsp;228-266.<br />
*<EM>Programming with Algebras</EM> by Richard B. Kieburtz and Jeffrey Lewis, p.&nbsp;267-307.<br />
*<EM>Graph Algorithms with a Functional Flavour</EM> by John Launchbury, p.&nbsp;308-331.<br />
<br />
[http://www.cse.ogi.edu/PacSoft/conf/summerschool96.html <EM>Advanced Functional Programming</EM>], Second International Summer School on Advanced Functional Programming Techniques, Evergreen State College, WA, USA, LNCS 1126, Springer-Verlag, 1996 (editors: J. Launchbury, E. Meijer, T. Sheard).<br />
*<EM>Composing the User Interface with Haggis</EM> by Sigbjorn Finne and Simon Peyton Jones, p.&nbsp;1-37.<br />
*<EM>Haskore Music Tutorial</EM> by Paul Hudak, p.&nbsp;38-67.<br />
*<EM>Polytypic Programming</EM> by Johan Jeuring and Patrick Jansson, p.&nbsp;68-114.<br />
*<EM>Implementing Threads in Standard ML</EM> by Peter Lee, p.&nbsp;115-130.<br />
*<EM>Functional Data Structures</EM> by Chris Okasaki, p.&nbsp;131-158.<br />
*<EM>Heap Profiling for Space Efficiency</EM> by Colin Runciman and Niklas R&ouml;jemo, p.&nbsp;159-183.<br />
*<EM&gt;Deterministic, Error-Correcting Combinator Parsers</EM> by S. Doaitse Swierstra and Luc Duponcheel, p.&nbsp;184-207.<br />
*<EM>Essentials of Standard ML Modules</EM> by Mads Tofte, p.&nbsp;208-238.<br />
<br />
[http://alfa.di.uminho.pt/~afp98/ Advanced Functional Programming, Third International School, AFP'98], <br />
in Braga, Portugal from 12th to 19th September 1998, LNCS 1608, Springer-Verlag, 1999<br />
(editors: D. Swierstra, P. Henriques and J. Oliveira).<BR><br />
All lecture notes and further material are available from the web site.<br />
<br />
= Foundations =<br />
<br />
Some books and links listed here can be found also in the articles of ''Theoretical foundations'' category<br />
* see [[Mathematics]]<br />
* or browse ''Theoretical foundations'' among [[Special:Categories]].<br />
<br />
;[http://www.dcs.qmul.ac.uk/~pt/Practical_Foundations/ Practical Foundations of Mathematics]<br />
:Paul Taylor. Cambridge University Press, ISBN: 0-521-63107-6, xii+576 pages, September 2000.<br />
<br />
;[http://www.cwru.edu/artsci/math/wells/pub/ttt.html Toposes, Triples and Theories]<br />
:Michael Barr and Charles Wells. The revised version of their formerly Springer Verlag published book is online for free download. Note that they use the name ''triple'' instead of ''monad''.<br />
<br />
=[[Research papers]]=<br />
<br />
A large collection of research papers published on various aspects of Haskell.<br />
<br />
<br />
[http://haskell.readscheme.org/ An Online Bibliography of Haskell research]<br />
:ReadScheme.org</div>Fishttps://wiki.haskell.org/index.php?title=Books&diff=5863Books2006-09-07T10:29:45Z<p>Fis: </p>
<hr />
<div>Books and tutorials covering many aspects of Haskell.<br />
<br />
=Language and library definition=<br />
<br />
<DL><br />
<DT>Simon Peyton Jones: [http://titles.cambridge.org/catalogue.asp?isbn=0521826144 <EM>Haskell 98 Language and Libraries</EM>], Cambridge University Press, 2003, Hardback, 272 pages, ISBN: 0521826144, £35.00<br />
<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
Haskell is the world's leading lazy functional programming language,<br />
widely used for teaching, research, and applications. The language<br />
continues to develop rapidly, but in 1998 the community decided to<br />
capture a stable snapshot of the language: Haskell 98. All Haskell<br />
compilers support Haskell 98, so practitioners and educators alike<br />
have a stable base for their work. This book constitutes the agreed<br />
definition of the Haskell 98, both the language itself and its<br />
supporting libraries. It has been considerably revised and refined<br />
since the original definition, and appears in print for the first<br />
time. It should be a standard reference work for anyone involved in<br />
research, teaching, or application of Haskell.<br />
</BLOCKQUOTE> <br />
The entire language definition is also available online:<br />
[[Language_and_library_specification|Language and library specification]]<br />
</DT><br />
</DL><br />
<br />
= Textbooks=<br />
<br />
<DL><br />
<DT>Paul Hudak: [http://www.haskell.org/soe <EM>The Haskell School of Expression: Learning Functional Programming through Multimedia</EM>], Cambridge University Press, New York, 2000, 416<br />
pp, 15 line diagrams, 75 exercises, Paperback $29.95, ISBN:<br />
0521644089, Hardback $74.95, ISBN: 0521643384<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
This book teaches functional programming as a way of thinking and<br />
problem solving, using Haskell, the most popular purely functional<br />
language. Rather than using the conventional mathematical examples<br />
commonly found in other programming language textbooks, the author<br />
draws examples from multimedia applications, including graphics,<br />
animation, and computer music, thus rewarding the reader with working<br />
programs for inherently more interesting applications. Aimed at both<br />
beginning and advanced programmers, this tutorial begins with a gentle<br />
introduction to functional programming and moves rapidly on to more<br />
advanced topics. An underlying theme is the design and implementation<br />
of domain specific languages, using three examples: FAL (a Functional<br />
Animation Language), IRL (an Imperative Robot Language), and MDL (a<br />
Music Description Language). Details about programming in Haskell<br />
are presented in boxes throughout the text so they can be easily<br />
referred to and found quickly.<br />
<br />
The book's Web Site contains source files for all programs in the<br />
text, as well as the graphics libraries to run them under Windows and<br />
Linux platforms. It also contains PowerPoint slides useful for<br />
teaching a course using the textbook.<br />
</blockquote><br />
<DT>Simon Thompson: [http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e/ <EM>Haskell: The Craft of Functional Programming</EM>], Second Edition,<br />
Addison-Wesley, 507&nbsp;pages, paperback, 1999. ISBN<br />
0-201-34275-8.<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
The second edition of Haskell: The Craft of Functional Programming is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on the process of crafting programs and the text contains many examples and running case studies, as well as advice an program design, testing, problem solving and how to avoid common pitfalls. <br />
<br />
Building on the strengths of the first edition, the book includes many new and improved features: <br />
*Complete coverage of Haskell 98, the standard version of Haskell which will be stable and supported by implementations for years to come. <br />
*An emphasis on software engineering principles, encouraging a disciplined approach to building reusable libraries of software components. <br />
*Detailed coverage of the Hugs interpreter with an appendix covering other implementations. <br />
*A running case study of pictures emphasizes the built-in functions which appear in the standard prelude and libraries. It is also used to give an early preview of some of the more complex language features, such as high-order functions. <br />
*List comprehensions and the standard functions over lists are covered before recursion. <br />
*Early coverage of polymorphism supporting the "toolkit" approach and encouraging the resuse of built-in functions and types. <br />
*Extensive reference material containing details of further reading in books, journals and on the World Wide Web. <br />
*Accompanying Web Site supporting the book, containing all the program code, further teaching materials and other useful resources. <br />
<B>Synopsis</B><BR> <br />
This books introduces Haskell at a level appropriate for those with little or no prior experience of functional programming. The emphasis is on the process of crafting programs, solving problems, and avoiding common errors.<br />
</blockquote><br />
<br />
<DT>Richard Bird: [http://www.prenhall.com/allbooks/ptr_0134843460.html <EM>Introduction to Functional Programming using Haskell</EM>], 2nd edition, Prentice Hall Press, 1998, 460 pp., ISBN: 0-13-484346-0.<br />
<blockquote><br />
From the cover:<br />
<br />
After the success of the first edition, Introduction to Functional Programming using Haskell has been thoroughly updated and revised to provide a complete grounding in the principles and techniques of programming with functions.<br />
<br />
The second edition uses the popular language Haskell to express functional programs. There are new chapters on program optimisation, abstract datatypes in a functional setting, and programming in a monadic style. There are completely new case studies, and many new exercises.<br />
<br />
As in the first edition, there is an emphasis on the fundamental techniques for reasoning about functional programs, and for deriving them systematically from their specifications.<br />
<br />
The book is self-contained, assuming no prior knowledge of programming, and is suitable as an introductory undergraduate text for first- or second-year students.<br />
</blockquote><br />
<br />
<DT>Antony Davie: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521277248 <EM>An Introduction to Functional Programming Systems Using Haskell</EM>], Cambridge University Press, 1992. ISBN 0-521-25830-8 (hardback). ISBN 0-521-27724-8 (paperback).<br />
<blockquote><br />
Cover:<br />
<br />
Functional programming is a style of programming that has become increasingly popular during the past few years.<br />
Applicative programs have the advantage of being almost immediately expressible as functional descriptions; they can<br />
be proved correct and transformed through the referential transparency property.<br />
<br />
This book presents the basic concepts of functional programming, using the language Haskell for examples. The author<br />
incorporates a discussion of lambda calculus and its relationship with Haskell, exploring the implications for<br />
raparallelism. Contents: SASL for Beginners / Examples of SASL Programming / More Advanced Applicative Programming<br />
Techniques / Lambda Calculus / The Relationship Between Lambda Calculus and SASL / Program Transformation and<br />
Efficiency / Correctness, Equivalence and Program Verification / Landin's SECD Machine and Related<br />
Implementations / Further Implementation Techniques / Special Purpose Hardware / The Applicative Style of<br />
Semantics / Other Applicative Languages / Implications for Parallelism / Functional Programming in Von Neumann<br />
Languages <br />
</blockquote><br />
<br />
<DT>Fethi Rabhi and Guy Lapalme: [http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html <EM> Algorithms: A functional programming approach</EM>], <br />
Addison-Wesley, 235&nbsp;pages, paperback, 1999. ISBN<br />
0-201-59604-0<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
The authors challenge more traditional methods of teaching algorithms<br />
by using a functional programming context, with Haskell as an<br />
implementation language. This leads to smaller, clearer and more<br />
elegant programs which enable the programmer to understand the<br />
algorithm more quickly and to use that understanding to explore<br />
alternative solutions. <br><br />
<b>Key features:</b><br />
*Most chapters are self-contained and can be taught independently from each other.<br />
*All programs are in Haskell'98 and provided on a WWW site.<br />
*End of chapter exercises throughout.<br />
*Comprehensive index and bibliographical notes.<br />
<B>Synopsis</B><BR> <br />
The book is organised as a classic algorithms book according to topics<br />
such as Abstract Data Types, sorting and searching. It uses a<br />
succession of practical programming examples to develop in the reader<br />
problem-solving skills which can be easily transferred to other<br />
language paradigms. It also introduces the idea of capturing<br />
algorithmic design strategies (e.g. Divide-and-Conquer, Dynamic<br />
Programming) through higher-order functions.<br><br />
<b>Target audience</b><br><br />
The book is intended for computer science students taking algorithms<br />
and/or (basic or advanced) functional programming courses.<br />
</BLOCKQUOTE><br />
<br />
<dt>Jeremy Gibbons and Oege de Moor (eds.): [http://www.palgrave.com/catalogue/catalogue.asp?Title_Id=0333992857 <em>The Fun of Programming</em>],Palgrave, 2002, 288 pages. ISBN 0333992857.<br />
<blockquote><br />
<b>Book description:</b><br><br />
In this textbook, leading researchers give tutorial expositions on the current state of the art of functional<br />
programming. The text is suitable for an undergraduate course immediately following an introduction to<br />
functional programming, and also for self-study. All new concepts are illustrated by plentiful examples,<br />
as well as exercises. A website gives access to accompanying software.<br />
</blockquote><br />
<br />
<dt> Cordelia Hall and John O'Donnell: [http://www.dcs.gla.ac.uk/~jtod/discrete-mathematics/ <em>Discrete Mathematics Using a Computer</em>],<br />
Springer, 2000, 360 pages. ISBN 1-85233-089-9.<br />
<blockquote><br />
<b>Book description:</b><br><br />
This book introduces the main topics of discrete mathematics with a strong emphasis on<br />
applications to computer science. It uses computer programs to implement and illustrate<br />
the mathematical ideas, helping the reader to gain a concrete understanding of the<br />
abstract mathematics. The programs are also useful for practical calculations, and they<br />
can serve as a foundation for larger software packages. <br />
<br />
Designed for first and second year undergraduate students, the book is also ideally suited<br />
to self-study. No prior knowledge of functional programming is required; the book and<br />
the online documentation provide everything you will need. <br />
</blockquote><br />
<br />
<dt>Kees Doets and Jan van Eijck: [http://www.cwi.nl/~jve/HR <em>The Haskell Road to Logic, Maths and Programming</em>]. King's College Publications, London, 2004. ISBN 0-9543006-9-6 (14.00 pounds, $25.00).<br />
<blockquote><br />
<b>Book description:</b><br><br />
The purpose of this book is to teach logic and mathematical reasoning<br />
in practice, and to connect logical reasoning with computer<br />
programming. Throughout the text, abstract concepts are linked to<br />
concrete representations in Haskell. Everything one has to know about<br />
programming in Haskell to understand the examples in the book is<br />
explained as we go along, but we do not cover every aspect of the<br />
language. Haskell is a marvelous demonstration tool for logic and<br />
maths because its functional character allows implementations to<br />
remain very close to the concepts that get implemented, while the<br />
laziness permits smooth handling of infinite data structures.<br />
<br />
We do not assume that our readers have previous experience with either<br />
programming or construction of formal proofs. We do assume previous<br />
acquaintance with mathematical notation, at the level of secondary<br />
school mathematics. Wherever necessary, we will recall relevant <br />
facts. Everything one needs to know about mathematical<br />
reasoning or programming is explained as we go along. We do assume<br />
that our readers are able to retrieve software from the Internet and<br />
install it, and that they know how to use an editor for constructing<br />
program texts.<br />
<br />
After having worked through the material in the book, i.e., after<br />
having digested the text and having carried out a substantial number<br />
of the exercises, the reader will be able to write interesting<br />
programs, reason about their correctness, and document them in a clear<br />
fashion. The reader will also have learned how to set up mathematical<br />
proofs in a structured way, and how to read and digest mathematical<br />
proofs written by others.<br />
<br />
The book can be used as a course textbook, but since it comes with<br />
solutions to all exercises (electronically available from the authors<br />
upon request) it is also well suited for private study. The source<br />
code of all programs discussed in the text, a list of errata, <br />
further relevant material and an email link to the authors<br />
can be found [http://www.cwi.nl/~jve/HR here].<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones: <em>Implementation of Functional Programming Language</em>,Prentice-Hall, 1987. ISBN 0134533259.<br />
<br />
<dt>Simon Peyton Jones, David Lester: <em>Implementing Functional Languages</em>, 1992.<br><br />
<blockquote><br />
The book is out of print. The full sources and a postscript version are <br />
[http://research.microsoft.com/Users/simonpj/Papers/papers.html available for free].<br />
</blockquote><br />
<br />
<dt>Simon Thompson: <em>Type Theory and Functional Programming</em>, Addison-Wesley, 1991. ISBN 0-201-41667-0.<br />
<blockquote><br />
Now out of print, the original version is available [http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ here].<br />
<br />
<em>Preface</em>:<br />
Constructive Type theory has been a topic of research interest to computer scientists,<br />
mathematicians, logicians and philosophers for a number of years. For computer scientists it provides<br />
a framework which brings together logic and programming languages in a most elegant and fertile way:<br />
program development and verification can proceed within a single system. Viewed in a different way,<br />
type theory is a functional programming language with some novel features, such as the totality of<br />
all its functions, its expressive type system allowing functions whose result type depends upon the<br />
value of its input, and sophisticated modules and abstract types whose interfaces can contain logical<br />
assertions as well as signature information. A third point of view emphasizes that programs (or<br />
functions) can be extracted from proofs in the logic.<br />
</blockquote><br />
<br />
</DL><br />
<br />
=Tutorials=<br />
<br />
==Introductions to Haskell==<br />
<br />
;[http://www.haskell.org/tutorial/ A Gentle Introduction to Haskell] <br />
:By Paul Hudak, John Peterson, and Joseph H. Fasel. The title is a bit misleading. Some knowledge of another functional programming language is expected. The emphasis is on the type system and those features which are really new in Haskell (compared to other functional programming languages). A classic.<br />
<br />
;[http://pub.hal3.name/daume02yaht.pdf Yet Another Haskell Tutorial]<br />
:By Hal Daume III et al. A recommended tutorial for Haskell that is still under construction but covers already much ground. Also a classic text.<br />
<br />
;[http://www.haskell.org/~pairwise/intro/intro.html Haskell Tutorial for C Programmers]<br />
:By Eric Etheridge. From the intro: "This tutorial assumes that the reader is familiar with C/C++, Python, Java, or Pascal. I am writing for you because it seems that no other tutorial was written to help students overcome the difficulty of moving from C/C++, Java, and the like to Haskell."<br />
<br />
;[http://www-106.ibm.com/developerworks/edu/os-dw-linuxhask-i.html Beginning Haskell] <br />
:From IBM developerWorks. This tutorial targets programmers of imperative languages wanting to learn about functional programming in the language Haskell. If you have programmed in languages such as C, Pascal, Fortran, C++, Java, Cobol, Ada, Perl, TCL, REXX, JavaScript, Visual Basic, or many others, you have been using an imperative paradigm. This tutorial provides a gentle introduction to the paradigm of functional programming, with specific illustrations in the Haskell 98 language. (Free registration required.)<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/teaching/Hskurs_toc.html Online Haskell Course] <br />
:By Ralf Hinze (in German).<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/tutorials.html Tutorial Papers in Functional Programming].<br />
:A collection of links to other Haskell tutorials, from John Hughes.<br />
<br />
;[http://www.cs.ou.edu/cs1323h/textbook/haskell.shtml Two Dozen Short Lessons in Haskell] <br />
:By Rex Page. A draft of a textbook on functional programming, available by ftp. It calls for active participation from readers by omitting material at certain points and asking the reader to attempt to fill in the missing information based on knowledge they have already acquired. The missing information is then supplied on the reverse side of the page. <br />
<br />
;[http://pleac.sourceforge.net/pleac_haskell/t1.html PLEAC-Haskell]<br />
:Following the Perl Cookbook (by Tom Christiansen and Nathan Torkington, published by O'Reilly) spirit, the PLEAC Project aims to gather fans of programming, in order to implement the solutions in other programming languages.<br />
<br />
;[ftp://ftp.geoinfo.tuwien.ac.at/navratil/HaskellTutorial.pdf Haskell-Tutorial] <br />
:By Damir Medak and Gerhard Navratil. The fundamentals of functional languages for beginners. <br />
<br />
;[http://en.wikibooks.org/wiki/Haskell Programming Haskell Wikibook] <br />
:A communal effort by several authors to produce the definitive Haskell textbook. Its very much a work in progress at the moment, and contributions are welcome.<br />
<br />
;[http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung Video Lectures] <br />
:Lectures (in English) by Jürgen Giesl. About 30 hours in total, and great for learning Haskell. The lectures are 2005-SS-FP.V01 through 2005-SS-FP.V26. Videos 2005-SS-FP.U01 through 2005-SS-FP.U11 are exercise answer sessions, so you probably don't want those.<br />
<br />
;[http://www.cs.utoronto.ca/~trebla/fp/ Albert's Functional Programming Course] <br />
:A 15 lesson introduction to most aspects of Haskell.<br />
<br />
;[http://www.iceteks.com/articles.php/haskell/1 Introduction to Haskell]<br />
:By Chris Dutton, An "attempt to bring the ideas of functional programming to the masses here, and an experiment in finding ways to make it easy and interesting to follow".<br />
<br />
;[http://www.csc.depauw.edu/~bhoward/courses/0203Spring/csc122/haskintro/ An Introduction to Haskell]<br />
:A brief introduction, by Brian Howard.<br />
<br />
;[http://web.syntaxpolice.org/lectures/haskellTalk/slides/index.html Introduction to Haskell]<br />
:By Isaac Jones (2003).<br />
<br />
;[http://www.linuxjournal.com/article/9096 Translating Haskell into English]<br />
:By Shannon Behrens, a glimpse of the Zen of Haskell, without requiring that they already be Haskell converts.<br />
<br />
===“Real world” tutorials===<br />
<br />
These tutorials examine using Haskell to writing complex real-wrold applications<br />
<br />
;[[Hitchhikers Guide to the Haskell]]<br />
: Tutorial for C/Java/OCaml/... programers by Dmitry Astapov. From the intro: "This text intends to introduce the reader to the practical aspects of Haskell from the very beginning (plans for the first chapters include: I/O, darcs, Parsec, QuickCheck, profiling and debugging, to mention a few)".<br />
<br />
;[http://haskell.org/haskellwiki/IO_inside Haskell I/O inside: Down the Rabbit's Hole]<br />
:By Bulat Ziganshin (2006), a comprehensive tutorial on using IO monad.<br />
<br />
;[http://research.microsoft.com/%7Esimonpj/Papers/marktoberdorf Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell]<br />
:Simon Peyton Jones. Presented at the 2000 Marktoberdorf Summer School. In "Engineering theories of software construction", ed Tony Hoare, Manfred Broy, Ralf Steinbruggen, IOS Press, ISBN 1 58603 1724, 2001, pp47-96. The standard reference for monadic IO in GHC/Haskell. <br><strong>Abstract:</strong>Functional programming may be beautiful, but to write real applications we must grapple with awkward real-world issues: input/output, robustness, concurrency, and interfacing to programs written in other languages.<br />
<br />
;[http://www.reid-consulting-uk.ltd.uk/docs/ffi.html A Guide to Haskell's Foreign Function Interface]<br />
:A guide to using the foreign function interface extension, using the rich set of functions in the Foreign libraries, design issues, and FFI preprocessors.<br />
<br />
===Older tutorials===<br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/manuals/haskeller.dvi.gz The Little Haskeller] <br />
:By Cordelia Hall and John Hughes. 9. November 1993, 26 pages. An introduction using the Chalmers Haskell B interpreter (hbi). Beware that it relies very much on the user interface of hbi which is quite different for other Haskell systems, and the tutorials cover Haskell 1.2 , not Haskell 98.<br />
<br />
;[http://www.cs.uu.nl/people/jeroen/courses/fp-eng.pdf Functional Programming]<br />
:By Jeroen Fokker, 1995. (153 pages, 600 KB). Textbook for learning functional programming with Gofer (an older implementation of Haskell). Here without Chapters&nbsp;6 and&nbsp;7.<br />
<br />
==Reference material==<br />
<br />
;[http://undergraduate.csse.uwa.edu.au/units/230.301/lectureNotes/tourofprelude.html A Tour of the Haskell Prelude (basic functions)] <br />
:By Bernie Pope and Arjan van IJzendoorn.<br />
<br />
;[http://cs.anu.edu.au/Student/comp1100/haskell/tourofsyntax.html Tour of the Haskell Syntax] <br />
:By Arjan van IJzendoorn.<br />
<br />
;[http://zvon.org/other/haskell/Outputglobal/index.html Haskell Reference] <br />
:By Miloslav Nic.<br />
<br />
;[http://members.chello.nl/hjgtuyl/tourdemonad.html A tour of the Haskell Monad functions]<br />
:By Henk-Jan van Tuyl.<br />
<br />
;[http://www.cse.unsw.edu.au/~en1000/haskell/inbuilt.html Useful Haskell functions]<br />
:An explanation for beginners of many Haskell functions that are predefined in the Haskell Prelude.<br />
<br />
;[http://haskell.org/ghc/docs/latest/html/libraries/ Documentation for the standard libraries]<br />
:Complete documentation of the standard Haskell libraries.<br />
<br />
;[http://www.haskell.org/haskellwiki/Category:Idioms Haskell idioms]<br />
:A collection of articles describing some common Haskell idioms. Often quite advanced.<br />
<br />
;[http://www.haskell.org/haskellwiki/Blow_your_mind Useful idioms]<br />
:A collection of short, useful Haskell idioms.<br />
<br />
;[http://www.haskell.org/haskellwiki/Programming_guidelines Programming guidelines]<br />
:Some Haskell programming and style conventions.<br />
<br />
== Motivation for using Haskell ==<br />
<br />
;[http://www.md.chalmers.se/~rjmh/Papers/whyfp.html Why Functional Programming Matters] <br />
:By [http://www.md.chalmers.se/~rjmh/ John Hughes], The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 - 107. Also in: David A. Turner (ed.): Research Topics in Functional Programming, Addison-Wesley, 1990, pp. 17 - 42.<BR> Exposes the advantages of functional programming languages. Demonstrates how higher-order functions and lazy evaluation enable new forms of modularization of programs.<br />
<br />
;[[Why Haskell matters]] <br />
:Discussion of the advantages of using Haskell in particular. An excellent article.<br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/224/index.html Higher-order + Polymorphic = Reusable] <br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. Unpublished, May 1997.<BR> <STRONG>Abstract:</STRONG> This paper explores how certain ideas in object oriented languages have their correspondents in functional languages. In particular we look at the analogue of the iterators of the C++ standard template library. We also give an example of the use of constructor classes which feature in Haskell 1.3 and Gofer.<br />
<br />
;[http://www-128.ibm.com/developerworks/java/library/j-cb07186.html Explore functional programming with Haskell]<br />
:Introduction to the benefits of functional programming in Haskell by Bruce Tate.<br />
<br />
==Analysis and design methods==<br />
<br />
See [[Analysis and design]].<br />
<br />
== Teaching Haskell == <br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/208/index.html Where do I begin? A problem solving approach to teaching functional programming]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. In Krzysztof Apt, Pieter Hartel, and Paul Klint, editors, First International Conference on Declarative Programming Languages in Education. Springer-Verlag, September 1997. <br> <STRONG>Abstract:</STRONG> This paper introduces a problem solving method for teaching functional programming, based on Polya's `How To Solve It', an introductory investigation of mathematical method. We first present the language independent version, and then show in particular how it applies to the development of programs in Haskell. The method is illustrated by a sequence of examples and a larger case study. <br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1995/214/index.html Functional programming through the curriculum]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]and Steve Hill. In Pieter H. Hartel and Rinus Plasmeijer, editors, Functional Programming Languages in Education, LNCS 1022, pages 85-102. Springer-Verlag, December 1995. <br> <STRONG>Abstract:</STRONG> This paper discusses our experience in using a functional language in topics across the computer science curriculum. After examining the arguments for taking a functional approach, we look in detail at four case studies from different areas: programming language semantics, machine architectures, graphics and formal languages. <br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/CK02a.html The Risks and Benefits of Teaching Purely Functional Programming in First Year]<br />
:By [http://www.cse.unsw.edu.au/~chak Manuel M. T. Chakravarty] and [http://www.cse.unsw.edu.au/~keller Gabriele Keller]. Journal of Functional Programming 14(1), pp 113-123, 2004. An earlier version of this paper was presented at Functional and Declarative Programming in Education (FDPE02). <br> <strong>Abstract</strong> We argue that teaching purely functional programming as such in freshman courses is detrimental to both the curriculum as well as to promoting the paradigm. Instead, we need to focus on the more general aims of teaching elementary techniques of programming and essential concepts of computing. We support this viewpoint with experience gained during several semesters of teaching large first-year classes (up to 600 students) in Haskell. These classes consisted of computer science students as well as students from other disciplines. We have systematically gathered student feedback by conducting surveys after each semester. This article contributes an approach to the use of modern functional<br />
languages in first year courses and, based on this, advocates the use of functional languages in this setting.<br />
<br />
==Using monads==<br />
<br />
See also the [[Monad]] HaskellWiki page with another list of tutorials (should this redundancy be removed? -- not sure...)<br />
<br />
;[http://db.ewi.utwente.nl/Publications/PaperStore/db-utwente-0000003696.pdf The Haskell Programmer's Guide to the IO Monad - Don't Panic.] <br />
:Stefan Klinger. This report scratches the surface of category theory, an abstract branch of algebra, just deep enough to find the monad structure. It seems well written.<br />
<br />
;[http://www.nomaware.com/monads/html/ All About Monads] <br />
:By Jeff Newbern. This tutorial aims to explain the concept of a monad and its application to functional programming in a way that is easy to understand and useful to beginning and intermediate Haskell programmers. Familiarity with the Haskell language is assumed, but no prior experience with monads is required. <br />
<br />
;[http://www-users.mat.uni.torun.pl/~fly/materialy/fp/haskell-doc/Monads.html What the hell are Monads?] <br />
:By Noel Winstanley. A basic introduction to monads, monadic programming and IO. This introduction is presented by means of examples rather than theory, and assumes a little knowledge of Haskell. <br />
<br />
;[http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm Monads for the Working Haskell Programmer -- a short tutorial]<br />
:By Theodore Norvell. <br />
<br />
;[http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html You Could Have Invented Monads! (And Maybe You Already Have.)]<br />
:A short tutorial on monads, introduced from a pragmatic approach, with less category theory references <br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/monads.html Systematic Design of Monads]<br />
:John Hughes & Magnus Carlsson. Many useful monads can be designed in a systematic way, by successively adding facilities to a trivial monad. The capabilities that can be added in this way include state, exceptions, backtracking, and output. Here we give a brief description of the trivial monad, each kind of extension, and sketches of some interesting operations that each monad supports.<br />
<br />
;[[Meet Bob The Monadic Lover]]<br />
:by Andrea Rossato. A by-the-author-supposed-to-be funny and short introduction to Monads, with code but without any reference to category theory: what monads look like and what they are useful for, from the perspective of a ... lover. (There is also the slightly more serious [[The Monadic Way]] by the same author.)<br />
<br />
See also [[Research papers/Monads and arrows]]<br />
<br />
==Using arrows==<br />
<br />
This topic has an own HaskellWiki page: [[Arrow]].<br />
<br />
;[http://www.haskell.org/arrows/ Arrows: A General Interface to Computation]<br />
:Ross Paterson's page on arrows.<br />
<br />
HaWiki's [http://haskell.org/hawiki/UnderstandingArrows UnderstandingArrows].<br />
<br />
Monad.Reader's [http://www.haskell.org/tmrwiki/ArrowsIntroduction ArrowsIntroduction] article.<br />
<br />
See also [[Research papers/Monads and arrows]]<br />
<br />
== Attribute grammars ==<br />
<br />
This topic has an own HakellWiki page: [[Attribute grammar]]<br />
<br />
== Categorical programming ==<br />
<br />
See its own HaskellWiki page: [[Category theory#Categorical programming]].<br />
<br />
== Data structures ==<br />
<br />
;[http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521663504 Purely Functional Data Structures]<br />
:[http://www.cs.columbia.edu/~cdo/ Chris Okasaki], 232 pp., Cambridge University Press, 1998. ISBN 0-521-63124-6<BR> From the cover: <BLOCKQUOTE> Most books on data structures assume an imperative language like C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures and data structure design techniques from the point of view of functional languages. It includes code for a wide assortment both of classical data structures and of data structures developed exclusively for functional languages.This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study. [http://www.cs.columbia.edu/~cdo/pfds-haskell.tar.gz Haskell source code for the book] </BLOCKQUOTE><br />
<br />
See [[Research papers/Data structures]]<br />
<br />
==Schools on advanced funtional programming==<br />
<br />
<EM>Advanced Functional Programming</EM>, First International Spring<br />
School on Advanced Functional Programming Techniques, Bastad, Sweden, LNCS 925, Springer-Verlag, 1995 (editors: J. Jeuring, E. Meijer).<br />
*<EM>Functional Parsers</EM> by Jeroen Fokker, p.&nbsp;1-23.<br />
*<EM>Monads for functional programming</EM> by Philip Wadler, p.&nbsp;24-52.<br />
*<EM>The Design of a Pretty-printing Library</EM> by John Hughes, p.&nbsp;52-96.<br />
*<EM>Functional Programming with Overloading and Higher-Order Polymorphism</EM>, Mark P. Jones, p.&nbsp;97-136.<br />
*<EM>Programming with Fudgets</EM> by Thomas Hallgren and Magnus Carlsson, p.&nbsp;137-182.<br />
*<EM>Constructing Medium Sized Efficient Functional Programs in Clean</EM> by Marko C.J.D. van Eekelen and Rinus J. Plasmeijer, p.&nbsp;183-227.<br />
*<EM>Merging Monads and Folds for Functional Programming</EM> by Erik Meijer and Johan Jeuring, p.&nbsp;228-266.<br />
*<EM>Programming with Algebras</EM> by Richard B. Kieburtz and Jeffrey Lewis, p.&nbsp;267-307.<br />
*<EM>Graph Algorithms with a Functional Flavour</EM> by John Launchbury, p.&nbsp;308-331.<br />
<br />
[http://www.cse.ogi.edu/PacSoft/conf/summerschool96.html <EM>Advanced Functional Programming</EM>], Second International Summer School on Advanced Functional Programming Techniques, Evergreen State College, WA, USA, LNCS 1126, Springer-Verlag, 1996 (editors: J. Launchbury, E. Meijer, T. Sheard).<br />
*<EM>Composing the User Interface with Haggis</EM> by Sigbjorn Finne and Simon Peyton Jones, p.&nbsp;1-37.<br />
*<EM>Haskore Music Tutorial</EM> by Paul Hudak, p.&nbsp;38-67.<br />
*<EM>Polytypic Programming</EM> by Johan Jeuring and Patrick Jansson, p.&nbsp;68-114.<br />
*<EM>Implementing Threads in Standard ML</EM> by Peter Lee, p.&nbsp;115-130.<br />
*<EM>Functional Data Structures</EM> by Chris Okasaki, p.&nbsp;131-158.<br />
*<EM>Heap Profiling for Space Efficiency</EM> by Colin Runciman and Niklas R&ouml;jemo, p.&nbsp;159-183.<br />
*<EM&gt;Deterministic, Error-Correcting Combinator Parsers</EM> by S. Doaitse Swierstra and Luc Duponcheel, p.&nbsp;184-207.<br />
*<EM>Essentials of Standard ML Modules</EM> by Mads Tofte, p.&nbsp;208-238.<br />
<br />
[http://alfa.di.uminho.pt/~afp98/ Advanced Functional Programming, Third International School, AFP'98], <br />
in Braga, Portugal from 12th to 19th September 1998, LNCS 1608, Springer-Verlag, 1999<br />
(editors: D. Swierstra, P. Henriques and J. Oliveira).<BR><br />
All lecture notes and further material are available from the web site.<br />
<br />
= Foundations =<br />
<br />
Some books and links listed here can be found also in the articles of ''Theoretical foundations'' category<br />
* see [[Mathematics]]<br />
* or browse ''Theoretical foundations'' among [[Special:Categories]].<br />
<br />
;[http://www.dcs.qmul.ac.uk/~pt/Practical_Foundations/ Practical Foundations of Mathematics]<br />
:Paul Taylor. Cambridge University Press, ISBN: 0-521-63107-6, xii+576 pages, September 2000.<br />
<br />
;[http://www.cwru.edu/artsci/math/wells/pub/ttt.html Toposes, Triples and Theories]<br />
:Michael Barr and Charles Wells. The revised version of their formerly Springer Verlag published book is online for free download. Note that they use the name ''triple'' instead of ''monad''.<br />
<br />
=[[Research papers]]=<br />
<br />
A large collection of research papers published on various aspects of Haskell.<br />
<br />
<br />
[http://haskell.readscheme.org/ An Online Bibliography of Haskell research]<br />
:ReadScheme.org</div>Fishttps://wiki.haskell.org/index.php?title=Monad&diff=5862Monad2006-09-07T10:28:05Z<p>Fis: </p>
<hr />
<div>{{Standard class|Monad|module=Control.Monad|module-doc=Control-Monad|package=base}}<br />
The '''Monad''' class is defined like this:<br />
<br />
<haskell><br />
class Monad m where<br />
(>>=) :: m a -> (a -> m b) -> m b<br />
(>>) :: m a -> m b -> m b<br />
return :: a -> m a<br />
fail :: String -> m a<br />
</haskell><br />
<br />
All instances of Monad should obey:<br />
<br />
<haskell><br />
return a >>= k = k a<br />
m >>= return = m<br />
m >>= (\x -> k x >>= h) = (m >>= k) >>= h<br />
</haskell><br />
<br />
Any Monad can be made a [[Functor]] by defining <br />
<br />
<haskell><br />
fmap ab ma = ma >>= (return . ab)<br />
</haskell><br />
<br />
However, the Functor class is not a superclass of the Monad class. See [[Functor hierarchy proposal]].<br />
<br />
== Monad Tutorials ==<br />
<br />
Monads are known for being deeply confusing to lots of people, so there are plenty of tutorials specifically related to monads. Each takes a different approach to Monads, and hopefully everyone will find something useful.<br />
<br />
* [[Monads as Containers]]<br />
* [http://www.nomaware.com/monads/html/index.html All About Monads]<br />
* [[Simple monad examples]]<br />
* [http://www.loria.fr/~kow/monads/index.html Of monads and space suits]<br />
* [http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html You could have invented monads]<br />
* [[Meet Bob The Monadic Lover]], or the slightly more serious [[The Monadic Way]]<br />
<br />
== Monad Reference Guides ==<br />
<br />
An explanation of the basic Monad functions, with examples, can be found in the reference guide [http://members.chello.nl/hjgtuyl/tourdemonad.html A tour of the Haskell Monad functions], by Henk-Jan van Tuyl.<br />
<br />
<br />
[[Category:Standard classes]]</div>Fishttps://wiki.haskell.org/index.php?title=The_Monadic_Way/Part_I&diff=5847The Monadic Way/Part I2006-09-06T12:02:38Z<p>Fis: </p>
<hr />
<div>'''Note: this is the first part of [[The Monadic Way]]'''<br />
==An evaluation of Philip Wadler's "Monads for functional programming"==<br />
<br />
This tutorial is a "translation" of Philip Wedler's [http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf "Monads for functional programming"].<br />
(avail. from [http://homepages.inf.ed.ac.uk/wadler/topics/monads.html here])<br />
<br />
I'm a Haskell newbie trying to grasp such a difficult concept as the<br />
one of Monad and monadic computation.<br />
<br />
While [http://www.cs.utah.edu/~hal/htut/ "Yet Another Haskell Tutorial"] <br />
gave me a good understanding of the type system when it<br />
comes to monads I find it almost unreadable.<br />
<br />
But I had also Wadler's paper, and started reading it. Well, just<br />
wonderful! It explains how to ''create'' a monad!<br />
<br />
So I decided to "translate it", in order to clarify to myself the<br />
topic. And I'm now sharing this traslation ('''not completed yet'')<br />
with the hope it will be useful to someone else.<br />
<br />
Moreover, that's a wiki, so please improve it. And, specifically,<br />
correct my poor English. I'm Italian, after all.<br />
<br />
'''Note: The source of this page can be used as a Literate Haskell<br />
file and can be run with ghci or hugs: so cut paste change and run (in<br />
emacs for instance) while reading it...'''<br />
<br />
==A Simple Evaluator==<br />
<br />
Let's start with something simple: suppose we want to implement a new<br />
programming language. We just finished with<br />
[http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/ Abelson and Sussman's Structure and Interpretation of Computer Programs] <br />
and we want to test what we have learned.<br />
<br />
Our programming language will be very simple: it will just compute the<br />
sum of two terms.<br />
<br />
So we have just one primitive operation (Add) that takes two constants<br />
and calculates their sum.<br />
<br />
Moreover we have just one kind of data type: Con a, which is an Int.<br />
<br />
For instance, something like:<br />
<br />
(Add (Con 5) (Con 6))<br />
<br />
should yeld:<br />
<br />
11<br />
<br />
===The basic evaluator===<br />
<br />
We will implement our language with the help of a data type<br />
constructor such as:<br />
<br />
<div id="BasicEval"><br />
<haskell><br />
<br />
> module TheMonadicWay where<br />
> data Term = Con Int<br />
> | Add Term Term<br />
> deriving (Show)<br />
<br />
</haskell><br />
<br />
After that we build our interpreter:<br />
<br />
<haskell><br />
<br />
> eval :: Term -> Int<br />
> eval (Con a) = a<br />
> eval (Add a b) = eval a + eval b<br />
<br />
</haskell><br />
<br />
That's it. Just an example:<br />
<br />
*TheMonadicWay> eval (Add (Con 5) (Con 6))<br />
11<br />
*TheMonadicWay><br />
<br />
Very very simple. The evaluator checks if its argument is of type Con<br />
Int: if it is it just returns the Int.<br />
<br />
If the argument is not of type Con, but it is of type Term, it<br />
evaluates the first Term and sums the result with the result of the<br />
evaluation of the second Term.<br />
<br />
== Some Output, Please!==<br />
<br />
Now, that's fine, but we'd like to add some features, like providing<br />
some output, to show how the computation was carried out.<br />
<br />
Well, but Haskell is a pure functional language, with no side effects,<br />
we were told.<br />
<br />
Now we seem to be wanting to create a side effect of the computation,<br />
its output, and be able to stare at it...<br />
<br />
If we had some global variable to store the out that would be<br />
simple...<br />
<br />
But we can create the output and carry it along the computation,<br />
concatenating it with the old one, and present it at the end of the<br />
evaluation together with the evaluation of the expression given to our<br />
evaluator/interpreter!<br />
<br />
===The basic evaluator with output===<br />
<br />
Simple and neat:<br />
<div id="BasivEvalO"><br />
<haskell><br />
<br />
> type MOut a = (a, Output)<br />
> type Output = String<br />
> <br />
> formatLine :: Term -> Int -> Output<br />
> formatLine t a = "eval (" ++ show t ++ ") <= " ++ show a ++ " - " <br />
> <br />
> evalO :: Term -> MOut Int<br />
> evalO (Con a) = (a, formatLine (Con a) a)<br />
> evalO (Add t u) = ((a + b),(x ++ y ++ formatLine (Add t u) (a + b)))<br />
> where (a, x) = evalO t<br />
> (b, y) = evalO u<br />
<br />
</haskell><br />
<br />
Now we have what we want. But we had to change our evaluator quite a<br />
bit. <br />
<br />
First we added a function, formatLine, that takes an argument of type<br />
Term (the expression to be evaluated), one of type Int (the result of<br />
the evaluation of Term) and gives back an output of type Output (that<br />
is a synonymous of String). This is just a helper function to format<br />
the string to output. Not very interesting at all.<br />
<br />
The evaluator itself changed quite a lot! Now it has a different type<br />
signature: it takes an argument of type Term and produces a new type,<br />
we called it MOut, that is actually a compound pair of a variable (of<br />
a variable) type a (an Int in our evaluator) and a type Output, a<br />
string.<br />
<br />
So our evaluator, now, will take a Term (the type of the expressions<br />
in our new programming language) and will produce a pair, composed of<br />
the result of the evaluation (an Int) and the Output, a string.<br />
<br />
So far so good. But what's happening inside the evaluator?<br />
<br />
The first part will just return a pair with the number evaluated and<br />
the output formatted by formatLine. <br />
<br />
The second part does something more complicated: it returns a pair<br />
composed by <br />
1. the result of the evaluation of the right Term summed to the result<br />
of the evaluation of the second Term<br />
2. the output: the concatenation of the output produced by the<br />
evaluation of the right Term, the output produced by the evaluation of<br />
the left Term (each this evaluation returns a pair with the number and<br />
the output), and the formatted output of the evaluation.<br />
<br />
Let's try it:<br />
*TheMonadicWay> evalO (Add (Con 5) (Con 6))<br />
(11,"eval (Con 5) <= 5 - eval (Con 6) <= 6 - eval (Add (Con 5) (Con 6)) <= 11 - ")<br />
*TheMonadicWay><br />
<br />
It works! Let's put the output this way:<br />
eval (Con 5) <= 5 - <br />
eval (Con 6) <= 6 - <br />
eval (Add (Con 5) (Con 6)) <= 11 -<br />
<br />
Great! We are able to produce a side effect of our evaluation and<br />
present it at the end of the computation, after all.<br />
<br />
Let's have a closer look at this expression:<br />
<haskell><br />
<br />
evalO (Add t u) = ((a + b),(x ++ y ++ formatLine (Add t u) (a + b)))<br />
where (a, x) = evalO t<br />
(b, y) = evalO u<br />
<br />
</haskell><br />
<br />
Why all that? The problem is that we need:<br />
* "a" and "b" to calculate their sum (a + b), that will be the first element of the compund pair rapresenting the type (MOut) our evaluator will return <br />
* "x and "y" (the output of each evaluation) to be concatenated with the ourput of formatLine by the expression (x ++ y ++ formatLine(...)): this will be the second element of the compound pair MOut, the string part.<br />
<br />
So we need to separate the pairs produced by "evalO t" and "evalO u".<br />
<br />
We do that within the where clause (remember: evalO now produces a value of type<br />
MOut Int, i.e. a pair of an Int and a String).<br />
<br />
Then we use the single element, "extraded" within the where clause, to<br />
return a new MOut composed by <br />
<br />
((a + b),(x ++ y ++ formatLine (Add t u) (a + b))).<br />
------ -------------------------------------<br />
Int Output = String<br />
<br />
== Let's Go Monadic==<br />
<br />
Is there a more general way of doing so?<br />
<br />
Let's analyze the evaluator from another perspective. From the type<br />
perspective.<br />
<br />
We solved our problem by creating a new type, a pair of an Int (the<br />
result of the evaluation) and a String (the output of the process of<br />
evaluation).<br />
<br />
The first part of the evaluator does nothing else but creating, from a<br />
value of type Int, an object of type MOut Int (Int,Output). It does so<br />
by creating a pair with that Int and some text produced by formatLine.<br />
<br />
The second part evaluates the two Term(s) and "stores" the values thus<br />
produced in some variables to be use later to compute the output.<br />
<br />
Let's focus on the "stores" action. The correct term should be<br />
"binds".<br />
<br />
Take a function:<br />
<haskell><br />
f x = x + x<br />
</haskell><br />
"x" appears on both sides of the expression. We say that on the right<br />
side "x" is bound to the value of x given on the left side.<br />
<br />
So<br />
<haskell><br />
f 3<br />
</haskell><br />
binds x to 3 for the evaluation of the expression "x + x".<br />
<br />
Our evaluator binds "a" and "x" / "b" and "y" with the evaluation of<br />
"evalO t" and "evalO u" respectively. <br />
<br />
Then "a","b","x" and "y" will be used in the evaluation of<br />
((a+b),(x++y++formatLine)), the will produce a value of type MOut Int:<br />
<br />
<pre><br />
<br />
((a + b),(x ++ y ++ formatLine (Add t u) (a + b))).<br />
------ -------------------------------------<br />
\ / \ /<br />
Int Output = String<br />
---------------------------------<br />
\ /<br />
MOut Int <br />
</pre><br />
<br />
The binding happens in the where clause:<br />
<haskell><br />
where (a, x) = evalO t<br />
(b, y) = evalO u<br />
</haskell><br />
<br />
We know that there is an ad hoc operator for binding variables to a<br />
value: lambda, or \.<br />
<br />
Indeed f x = x + x is syntactic sugar for:<br />
<haskell><br />
f = \x -> x + x<br />
</haskell><br />
When we write f 3 we are actually binding "x" to 3 within what's next<br />
"->", that will be used (substituted) for evaluating f 3.<br />
<br />
So we can try to abstract this phenomenon.<br />
<br />
===Monadic evaluator with output===<br />
What we need is a function that takes our composed type MOut Int and a<br />
function in order to produce a new MOut Int, concatenating the<br />
output of the computation of the first with the output of the<br />
computation of the second.<br />
<br />
This is what bindM does:<br />
<br />
<haskell><br />
<br />
> bindM :: MOut a -> (a -> MOut b) -> MOut b<br />
> bindM m f = (b, x ++ y)<br />
> where (a, x) = m<br />
> (b, y) = f a<br />
<br />
</haskell><br />
<br />
It takes:<br />
* "m": the compound type MOut Int carrying the result of an "eval Term",<br />
* a function "f". This function will take the Int ("a") extracted by the evaluation of "m" ((a,x)=m). This function will produce a new pair: a new Int produced by a new evaluation; some new output.<br />
<br />
bindM will return the new Int in pair with the concatenated outputs<br />
resulting from the evaluation of "m" and "f a".<br />
<br />
As you see, we took the binding part out from evalO and put it in this new function.<br />
<br />
So let's write the new version of the evaluator, that we will call evalM_1:<br />
<br />
<haskell><br />
<br />
> evalM_1 :: Term -> MOut Int<br />
> evalM_1 (Con a) = (a, formatLine (Con a) a)<br />
> evalM_1 (Add t u) = bindM (evalM_1 t) (\a -> <br />
> bindM (evalM_1 u) (\b -> <br />
> ((a + b), formatLine (Add t u) (a + b))<br />
> )<br />
> )<br />
<br />
</haskell><br />
<br />
Ugly, isn't it?<br />
<br />
Let's start from the outside:<br />
<br />
<haskell><br />
bindM (evalM_1 u) (\b -> ((a + b), formatLine (Add t u) (a + b)))<br />
</haskell><br />
<br />
bindM takes the result of the evaluation "evalM_1 u", a type Mout Int,<br />
and a function. It will extract the Int from that type and use it to<br />
bind "b".<br />
<br />
So in bindM (evalM_1 u) (\b ->) "b" will be bound to the value<br />
returned by evalM_1 u, and this bounded variable will be available in<br />
what comes after "->" as a bounded variable (not free).<br />
<br />
Then the outer part (bindM (evalM_1 t) (\a...) will bind "a" to the<br />
value returned "evalM_1 t", the result of the evaluatuion of the first<br />
Term. This value is needed to evaluate "((a+b), formatLine...) and<br />
produce our final MOut Int.<br />
<br />
S we can use lambda notation to write our evaluator in a more convinient way:<br />
<br />
<haskell><br />
<br />
> evalM_2 :: Term -> MOut Int<br />
> evalM_2 (Con a) = (a, formatLine (Con a) a)<br />
> evalM_2 (Add t u) = evalM_2 t `bindM` \a -><br />
> evalM_2 u `bindM` \b -><br />
> ((a + b), (formatLine (Add t u) (a + b)))<br />
<br />
</haskell><br />
<br />
Now, look at the first part:<br />
<br />
<haskell><br />
evalM_2 (Con a) = (a, formatLine (Con a) a)<br />
</haskell><br />
<br />
We could use a more general way of creating some output. <br />
<br />
We can create a function that takes an Int and returns the type MOut<br />
Int. we do that by pairing the received Int with an empty string "".<br />
<br />
This will be a general way of creating an object with type MOut Int starting from an Int.<br />
<br />
Or, more generaly, a function that takes something of a variable type<br />
a, and return an object of type MOut a, a coumpunt object made up of<br />
an element of type a, and one of type String.<br />
<br />
There it is:<br />
<br />
<haskell><br />
<br />
> mkM :: a -> MOut a<br />
> mkM a = (a, "")<br />
<br />
</haskell><br />
<br />
Then we need a method of inserting some text in our object of type<br />
MOut. So we will take a string and return it paired with a void<br />
element "()":<br />
<br />
<haskell><br />
<br />
> outPut :: Output -> MOut ()<br />
> outPut x = ((), x)<br />
<br />
</haskell><br />
<br />
Very simple: we have a string "x" (Output) and create a pair with a ()<br />
instead of an Int, and the output.<br />
<br />
Now we can rewrite:<br />
<haskell><br />
evalM_2 (Con a) = (a, formatLine (Con a) a)<br />
</haskell><br />
using the bindM function:<br />
<haskell><br />
evalM_2 (Con a) = outPut (formatLine (Con a) a) `bindM` \_ -> mkM a<br />
</haskell><br />
<br />
First we create an object of type MOut with the Int part (). As you<br />
see bindM will not use it ("\_"), but will concatenate the String part<br />
with the result of mkM, which in turn is the empry string "".<br />
<br />
In other words, first we insert the Output part (a string) in our MOut<br />
Int type, and then we insert the Int.<br />
<br />
Let's rewrite the evaluator:<br />
<br />
<haskell><br />
<br />
> evalM_3 :: Term -> MOut Int<br />
> evalM_3 (Con a) = outPut (formatLine (Con a) a) `bindM` \_ -> <br />
> mkM a<br />
> evalM_3 (Add t u) = evalM_3 t `bindM` \a -><br />
> evalM_3 u `bindM` \b -><br />
> outPut (formatLine (Add t u) (a + b)) `bindM` \_ -> <br />
> mkM (a + b)<br />
<br />
</haskell><br />
<br />
Well, this is fine, definetly better then before, anyway.<br />
<br />
Still we use `bindM` \_ -> that binds something we do not use (_). We<br />
could write something for this case, when we concatenate computations<br />
without the need of binding variables. Let's call it `combineM`:<br />
<br />
<haskell><br />
<br />
> combineM :: MOut a -> MOut b -> MOut b<br />
> combineM m f = m `bindM` \_ -> f<br />
<br />
</haskell><br />
<br />
So the new evaluator:<br />
<br />
<haskell><br />
<br />
> evalM :: Term -> MOut Int<br />
> evalM (Con a) = outPut (formatLine (Con a) a) `combineM` <br />
> mkM a<br />
> evalM (Add t u) = evalM t `bindM` \a -><br />
> evalM u `bindM` \b -><br />
> outPut (formatLine (Add t u) (a + b)) `combineM` <br />
> mkM (a + b)<br />
<br />
</haskell><br />
<br />
Let's put everything together (and change some names changing M into<br />
MO, so that this file will be still usable as a Literate Haskell<br />
file):<br />
<br />
<haskell><br />
<br />
> type MO a = (a, Out)<br />
> type Out = String<br />
<br />
> mkMO :: a -> MO a<br />
> mkMO a = (a, "")<br />
<br />
> bindMO :: MO a -> (a -> MO b) -> MO b<br />
> bindMO m f = (b, x ++ y)<br />
> where (a, x) = m<br />
> (b, y) = f a<br />
<br />
> combineMO :: MO a -> MO b -> MO b<br />
> combineMO m f = m `bindM` \_ -> f<br />
<br />
> outMO :: Out -> MO ()<br />
> outMO x = ((), x)<br />
<br />
> evalMO :: Term -> MO Int<br />
> evalMO (Con a) = outMO (formatLine (Con a) a) `combineMO`<br />
> mkMO a<br />
> evalMO (Add t u) = evalMO t `bindMO` \a -><br />
> evalMO u `bindMO` \b -><br />
> outMO (formatLine (Add t u) (a + b)) `combineMO` <br />
> mkMO (a + b)<br />
<br />
</haskell><br />
<br />
==What Does Bind Bind?==<br />
<br />
<div id="Bind"><br />
The evaluator looks like:<br />
<haskell><br />
evalM t >>= \a -> evalM u >>= \b -> outPut "something" >>= \_ -> mkM (a +b)<br />
</haskell><br />
where >>= is bindMO, obviously.<br />
<br />
Let's do some substitution, writing the type of their output of each function:<br />
* evalMO t => (a,Out) - where a is Int<br />
* evalMO u => (b,Out) - where b is the same of a, an Int, but with a different value<br />
* outMO Out = ((),Out)<br />
* mkMO (a+b) => ((a+b),Out) - where (a+b) is the same of a and b, but with a different value from either a and b<br />
<br />
<pre><br />
B | (a,Out) >>= \a -> (b,Out) >>= \b -> ((),Out) >>= \_ >>= ((a + b), Out)---\<br />
i | V V V V V V V V ^ ^ ^ ^ |\<br />
n | |__|________^ | | ^ | | | | | | | MOut Int <=> ((a+b), Out)<br />
d |_____|__(++)__|_Out_|__|__(++)__V_Out_|___|___(++)_|_(++)__|___|____|_____|/<br />
i | | |______(b)__|_____|_____(b)____|__(b)__|___|<br />
n | |_________(a)___________|____________|__(a)__|<br />
g | |_____()_____|<br />
<br />
</pre><br />
<br />
Clear, isn't it?<br />
<br />
"bindMO" is just a function that takes care of gluing together, inside<br />
a data type, a sequence of computations!<br />
<br />
== Some Sugar, Please!==<br />
Now our evaluator has been completely transformed into a monadic<br />
evaluator. That's what it is: a monad.<br />
<br />
We have a function that constructs an object of type MO Int, formed by<br />
a pair: the result of the evaluation and the accumulated<br />
(concatenated) output.<br />
<br />
The process of accumulation and the act of parting the MO Int into its<br />
component is buried into bindMO, now, that can also preserve some<br />
value for later uses.<br />
<br />
So we have:<br />
* MO a type constructor for a type carrying a pair composed by an Int and a String;<br />
* bindMO, that gives a direction to the process of evaluation: it concatenates computations and captures some side effects we created (the direction is given by the changes in the Out part: there's a "before" when Out was something and there's a "later" when Out is something else).<br />
* mkMO lets us create an object of type MO Int starting from an Int.<br />
<br />
As you see this is all we need to create a monad. In other words<br />
monads arise from the type system and the lambda calculus. Everything<br />
else is just syntactic sugar.<br />
<br />
So, let's have a look at that sugar: the famous do-notation!<br />
<br />
===Basic monadic evaluator in do-notation===<br />
<br />
We will now rewrite our [[The Monadic Way Part I#BasicEval|basic evaluator]] using the do-notation.<br />
<br />
Now we have to crate a new type: this is necessary in order to use<br />
specific monadic notation and have at our disposal the more practical<br />
do-notation ('''below we will see the consequences of doing so!'''):<br />
<br />
<haskell><br />
<br />
> newtype Eval a = Eval a<br />
> deriving (Show)<br />
<br />
</haskell><br />
<br />
So, our type will be an instance of the monad class. We will have to<br />
define the methods of this class (>>= and return), but that will be<br />
easy since we have already done that when defining bindMO and mkMO:<br />
<br />
<haskell><br />
<br />
> instance Monad Eval where<br />
> return a = Eval a<br />
> Eval m >>= f = f m<br />
<br />
</haskell><br />
<br />
You can see that return will create, from an argument of a variable<br />
type a (in our case that will be an Int) an object of type Eval Int,<br />
that carries inside just an Int, the result of the evaluation of a<br />
Con.<br />
<br />
Bind (>>=) will match for an object of type Eval, extracting what's<br />
inside ("m") and will bind "m" in "f". We know that "f" must return an<br />
object of type Eval with inside an Int resulted by the computations<br />
made by "f" over "m" (that is to say, computations made by "f" where<br />
"f" is a functions with variables, and one of those variables is bound<br />
to the value resulting from the evaluation of "m").<br />
<br />
In exchange for doing so we will now be able to take the old version<br />
of our evaluator and substitute `bindMO` with >>= and `mkMO` with<br />
return: <br />
<br />
<haskell><br />
<br />
> evalM_4 :: Term -> Eval Int<br />
> evalM_4 (Con a) = return a<br />
> evalM_4 (Add t u) = evalM_4 t >>= \a -><br />
> evalM_4 u >>= \b -><br />
> return (a + b)<br />
<br />
</haskell><br />
<br />
which is equivalent, in the do-notation, to:<br />
<br />
<haskell><br />
<br />
> evalM_5 :: Term -> Eval Int<br />
> evalM_5 (Con a) = return a<br />
> evalM_5 (Add t u) = do a <- evalM_5 t<br />
> b <- evalM_5 u<br />
> return (a + b)<br />
<br />
</haskell><br />
<br />
Simple: <hask>do</hask> binds the result of "eval_M5 t" to "a", binds<br />
the result of "eval_M5 u" to "b" and then returns the sum of "a" and<br />
"b". In a very imperative style.<br />
<br />
===Monadic evaluator with output in do-notation===<br />
<br />
We can now have an image of what our monad should be, if we want it to<br />
produce output: it is out type (Eval) that is made up of a pair, and<br />
Int and a String called Output.<br />
<br />
During evaluation the first member of the pair (the Int) will "store"<br />
the results of our computation (i.e.: the procedures to calculate the<br />
final result). The second part, the String called Output, will get<br />
filled up with the concatenated output of the computation.<br />
<br />
The sequencing done by bindMO (now >>=) will take care of passing to<br />
the next evaluation the needed (way to calculate the) Int and will do<br />
some more side calculation to produce the output (concatenating<br />
outputs resulting from computation of the new Int, for instance).<br />
<br />
So we can grasp the basic concept of a monad: it is like a label which<br />
we attach to each step of the evaluation (the String attached to the<br />
Int). <br />
This label is persistent within the process of computation and at each<br />
step bindMO can do some manipulation of it.<br />
We are creating side-effects and propagating them within our monads.<br />
<br />
Ok. Let's translate our output-producing evaluator in monadic<br />
notation:<br />
<br />
<div id="MonadicEvalIO"><br />
<haskell><br />
<br />
> newtype Eval_IO a = Eval_IO (a, O)<br />
> deriving (Show)<br />
> type O = String<br />
<br />
> instance Monad Eval_IO where<br />
> return a = Eval_IO (a, "")<br />
> (>>=) m f = Eval_IO (b, x ++ y)<br />
> where Eval_IO (a, x) = m<br />
> Eval_IO (b, y) = f a<br />
> print_IO :: O -> Eval_IO ()<br />
> print_IO x = Eval_IO ((), x)<br />
<br />
> eval_IO :: Term -> Eval_IO Int<br />
> eval_IO (Con a) = do print_IO (formatLine (Con a) a)<br />
> return a<br />
> eval_IO (Add t u) = do a <- eval_IO t<br />
> b <- eval_IO u<br />
> print_IO (formatLine (Add t u) (a + b))<br />
> return (a + b)<br />
<br />
</haskell><br />
<br />
Let's see the evaluator with output in action:<br />
*TheMonadicWay> eval_IO (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12)))) <br />
Eval_IO (54,"eval (Con 6) <= 6 - eval (Con 16) <= 16 - eval (Con 20) <= 20 - eval (Con 12) <= 12 - \<br />
eval (Add (Con 20) (Con 12)) <= 32 - eval (Add (Con 16) (Add (Con 20) (Con 12))) <= 48 - \<br />
eval (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12)))) <= 54 - ")<br />
*TheMonadicWay> <br />
<br />
Let's format the output part:<br />
eval (Con 6) <= 6 <br />
eval (Con 16) <= 16 <br />
eval (Con 20) <= 20 <br />
eval (Con 12) <= 12 <br />
eval (Add (Con 20) (Con 12)) <= 32 <br />
eval (Add (Con 16) (Add (Con 20) (Con 12))) <= 48 <br />
eval (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12)))) <= 54 <br />
<br />
==What Happened to Our Output??==<br />
<br />
Well, actually something happened to the output. Let's compare the<br />
output of evalMO (the monadic evaluator written without the<br />
do-notation) and eval_IO:<br />
<br />
*TheMonadicWay> evalMO (Con 6)<br />
(6,"eval (Con 6) <= 6 - ")<br />
*TheMonadicWay> eval_IO (Con 6)<br />
Eval_IO (6,"eval (Con 6) <= 6 - ")<br />
*TheMonadicWay> <br />
<br />
They look almost the same, but they are not the same: the output of<br />
eval_IO has the Eval_IO stuff. It must be related to the changes we<br />
had to do to our evaluator in order to use the do-conation, obviously.<br />
<br />
What's changed?<br />
<br />
First the type definition. We have now:<br />
<br />
<haskell><br />
newtype Eval_IO a = Eval_IO (a, O)<br />
deriving (Show)<br />
</haskell><br />
<br />
instead of <br />
<br />
<haskell><br />
type MO a = (a, Out)<br />
</haskell><br />
<br />
Moreover our bindMO and mkMO functions changed too, to reflect the<br />
change of the type definition:<br />
<br />
<haskell><br />
instance Monad Eval_IO where<br />
return a = Eval_IO (a, "")<br />
(>>=) m f = Eval_IO (b, x ++ y)<br />
where Eval_IO (a, x) = m<br />
Eval_IO (b, y) = f a<br />
</haskell><br />
<br />
Now <hask>return a</hask> is the product of the application of the<br />
type constructor Eval_IO to the pair that are going to form our monad.<br />
<br />
"return" takes an Int and insert it into our monad. It will also<br />
insert an empty String "" that (>>=) or (>>) will then concatenate in<br />
the sequence of computations they glue together.<br />
<br />
The same for (>>=): it will now return something constructed by<br />
Eval_IO: "b", the result of the application of "f" to "a" (better, the<br />
binding of "a" in "f") and "x" (matched by <hask>Eval_IO (a, x)</hask> with<br />
the evaluation of "m") and "y", (matched by "Eval_IO(b,y)" with the<br />
evaluation of "f a".<br />
<br />
That is to say: in the "where" clause, we are matching for the<br />
elements paired in a type Eval_IO: this is indeed the type of "m"<br />
(corresponding to "eval_IO t" in the body of the evaluator) and "f a"<br />
(where "f" correspond to another application of "eval_IO" to the<br />
result of the previous application of "m").<br />
<br />
And so, "Eval_IO (a,x) = m" means: match "a" and "x", paired in a type<br />
Eval_IO, and that are produced by the evaluation of "m" (that is to<br />
say: "eval_IO t"). The same for Eval_IO (b,y): match "b" and "y"<br />
produced by the evaluation of "f a".<br />
<br />
So the output of the evaluator is now not simply a pair made of and<br />
Int and a String. It is a specific type (Eval_IO) that happens to<br />
carry a pair of an Int and a String. But, if we want the Int and the<br />
string, we have to extract them from the Eval_IO type, as we do in the<br />
"where" clause: we ''unpack'' our type object (let's call it with its<br />
name: our monad!) and take out the Int and the String to feed the next<br />
function application and the output generation.<br />
<br />
The same to insert something in our monad: if we want to create a pair<br />
of an Int and a String, pair of type Eval_IO, we now have to ''pack''<br />
the together by using our type constructor, feeding it with pair<br />
composed by and Int and a String. This is what we do with the "return"<br />
method of out monad and with "print_IO" function, where:<br />
* return insert into the monad an Int;<br />
* print_IO insert into the monad a String.<br />
<br />
Notice that "combineM" disappeared. This is because it comes for free<br />
by just defining our type Eval_IO as an instance of the Monad class.<br />
<br />
Indeed, if we look at the definition of the Monad class in the Prelude we read:<br />
<haskell><br />
class Monad m where<br />
return :: a -> m a<br />
(>>=) :: m a -> (a -> m b) -> m b<br />
(>>) :: m a -> m b -> m b<br />
fail :: String -> m a<br />
<br />
-- Minimal complete definition: (>>=), return<br />
p >> q = p >>= \ _ -> q<br />
fail s = error s<br />
</haskell><br />
<br />
You can see that the "combineM"" method (or (>>)) is automatically derived by<br />
the "bindMO" (or >>=) method:<br />
<br />
<haskell><br />
p >> q = p >>= \ _ -> q<br />
</haskell><br />
<br />
So, what the hell is the old <hask>type MO a = (a, Out)</hask> that<br />
did not required all this additional work (apart the need to<br />
specifically define (>>)? <br />
<br />
Thanks the help of some nice guy of the<br />
[http://www.haskell.org/mailman/listinfo/haskell-cafe haskell-cafe mailing list]<br />
(look at the thread started by <br />
[http://www.haskell.org/pipermail/haskell-cafe/2006-August/017634.html this silly question of mine])<br />
we can answer.<br />
<br />
Type MO is just a synonymous for (a,Out): the two can be substituted<br />
one for the other. That's it.<br />
<br />
We did not have to pack "a" and "Out" together with a type constructor<br />
to have a new type MO.<br />
<br />
As a consequence, we cannot use MO as an instance of Monad, and so, we<br />
cannot use with it the syntactic sugar we needed: the do-notation.<br />
<br />
That is to say: a type created with the "type" keyword cannot be an<br />
instance of a class, and cannot inherits its methods (in our case<br />
(>>=, >> and return). And without those methods the do-notation is not<br />
usable.<br />
<br />
Anyway we will better understand all the far reaching consequences of<br />
this new approach later on.<br />
<br />
==Errare Monadicum Est==<br />
<br />
Now that we have a basic understanding of what a monad is, and does,<br />
we will further explore it by making some changes to our evaluator.<br />
<br />
In this section we will se how to handle exceptions in our monadic<br />
evaluator.<br />
<br />
Suppose that we want to stop the execution of our monad if some<br />
conditions occurs. If our evaluator was to compute divisions, instead<br />
of sums, then we would like to stop the evaluator when a division by<br />
zero occurs, possibly producing some output, instead of the result of<br />
the evaluation of the expression, that explains what happened.<br />
<br />
Basic error handling.<br />
<br />
We will do so starting from the beginning once again...<br />
<br />
===The basic evaluator, non monadic, with exception===<br />
<br />
We just take our basic evaluator, without any output, and write a<br />
method to stop execution if a condition occurs: <br />
<br />
<haskell><br />
<br />
> data M a = Raise Exception<br />
> | Return a<br />
> deriving (Show)<br />
> type Exception = String<br />
<br />
</haskell><br />
<br />
Now, our monad is of datatype "M a" which can either be constructed<br />
with the "Raise" constructor, that takes a String (Exception is a<br />
synonymous of String), or by the "Return" constructor, that takes a<br />
variable type ("a"), an Int in our case.<br />
<br />
<haskell><br />
<br />
> evalE :: Term -> M Int<br />
> evalE (Con a) = Return a<br />
<br />
</haskell><br />
<br />
If evalE matches a Con it will construct a type Return with, inside, the content of the Con.<br />
<br />
<haskell><br />
<br />
> evalE (Add a b) = <br />
> case evalE a of<br />
> Raise e -> Raise e<br />
> Return a -><br />
> case evalE b of <br />
> Raise e -> Raise e<br />
> Return b -><br />
> if (a+b) == 42<br />
> then Raise "The Ultimate Answer Has Been Computed!! Now I'm tired!"<br />
> else Return (a+b)<br />
<br />
</haskell><br />
<br />
If evalE matches an Add it will check if evaluating the first part<br />
produces a "Raise" or a "Return": in the first case it will return a<br />
"Raise" whose content is the same received. <br />
<br />
If instead the evaluation produces a value of a type matched by<br />
"Return", the evaluator will evaluate the second term of Add.<br />
<br />
If this returns a "Raise", a "Raise" will be returned all the way up<br />
the recursion, otherwise the evaluator will check whether a condition<br />
for raising a "Raise" exists. If not, it will return a "Return" with<br />
the sum inside.<br />
<br />
Test it with:<br />
<br />
evalE (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2)))<br />
<br />
<br />
===The basic evaluator, monadic, with exceptions===<br />
<br />
In order to produce a monadic version of the previous evaluator, the<br />
one that raises exceptions, we just need to abstract out from the<br />
evaluator all that case analysis.<br />
<br />
<haskell><br />
<br />
> data M1 a = Except Exception<br />
> | Ok {showM :: a }<br />
> deriving (Show)<br />
<br />
</haskell><br />
<br />
The data type didn't change at all. Well, we changed the name of the<br />
Return type constructor (now Ok) so that this constructor can coexist<br />
with the previous one in the same Literate Haskell file.<br />
<br />
<div id="MonadicEvalE"><br />
<haskell><br />
<br />
> instance Monad M1 where<br />
> return a = Ok a<br />
> m >>= f = case m of<br />
> Except e -> Except e<br />
> Ok a -> f a<br />
<br />
</haskell><br />
<br />
Binding operations are now very easy. Basically we check:<br />
* if the result of the evaluation of "m" produces an exception (first match: Except e ->...), in which case we return its content by constructing our M1 Int with the "Raise" constructor".<br />
* if the result of the evaluation of "m" is matched with the "Ok" constructor, we get its content and use it to bind the argument of "f" to its value.<br />
<br />
<hask>return a</hask> will just use the Ok type constructor for<br />
inserting "a" (in our case an Int) into M1 Int, the type of our monad.<br />
<br />
<haskell><br />
<br />
> raise :: Exception -> M1 a<br />
> raise e = Except e<br />
<br />
</haskell><br />
<br />
This is just a helper function to construct our "M1 a" type with the<br />
Raise constructor. It takes a string and returns a type (M1 a) to be<br />
matched with the "Raise" constructor.<br />
<br />
<haskell><br />
<br />
> eval_ME :: Term -> M1 Int<br />
> eval_ME (Con a) = do return a<br />
> eval_ME (Add t u) = do a <- eval_ME t<br />
> b <- eval_ME u<br />
> if (a+b) == 42<br />
> then raise "The Ultimate Answer Has Been Computed!! Now I'm tired!"<br />
> else return (a + b)<br />
<br />
</haskell><br />
<br />
The evaluator itself is very simple. We bind "a" with the result of<br />
"eval_ME t", "b" with the result of "eval_ME u", and we check for a<br />
condition: <br />
* if the condition is met we raise an exception, that is to say: we return a value constructed with the "Raise" constructor. This value will be matched by ">>=" in the next recursion. And >>= will just return it all the way up the recursion.<br />
* if the condition is not me, we return a value constructed with the "Return" type constructor and go on with the recursion...<br />
<br />
Run with:<br />
<br />
eval_ME (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2)))<br />
<br />
It is noteworthy the fact that in our datatype definition we used a<br />
label field with a label selector (we called it showM), even though it<br />
was not used in our code. We will use this methodology later on.<br />
<br />
So, just to refresh your memory:<br />
<br />
<haskell><br />
<br />
> data Person = Person {name :: String,<br />
> age :: Int,<br />
> hobby :: String<br />
> } deriving (Show)<br />
<br />
> andreaRossato = Person "Andrea" 37 "Haskell The Monadic Way"<br />
> personName (Person a b c) = a<br />
<br />
</haskell><br />
<br />
will produce:<br />
*TheMonadicWay> andreaRossato<br />
Person {name = "Andrea", age = 37, hobby = "Haskell The Monadic Way"}<br />
*TheMonadicWay> personName andreaRossato<br />
"Andrea"<br />
*TheMonadicWay> name andreaRossato<br />
"Andrea"<br />
*TheMonadicWay> age andreaRossato<br />
37<br />
*TheMonadicWay> hobby andreaRossato<br />
"Haskell The Monadic Way"<br />
*TheMonadicWay> <br />
<br />
<br />
===Monadic evaluator with output and exceptions===<br />
<br />
We will now try to combine the [[The Monadic Way Part I#MonadicEvalIO|output-producing monadic evaluator]] <br />
with [[The Monadic Way Part I#MonadicEvalE| exception producing one]].<br />
<br />
<br />
<haskell><br />
<br />
> data M2 a = Ex Exception<br />
> | Done {unpack :: (a,O) }<br />
> deriving (Show)<br />
<br />
</haskell><br />
<br />
Now we need a datatype with two constructor: one to produce a value<br />
type "M2 a" using "Ex String" and one for value type "M2 a" (Int in<br />
this case) using "Done a".<br />
<br />
'''Note''' that we changed the name of the exception type constructor<br />
from "Raise" to "Ex" just to make the two coexist in the same Literate<br />
Haskell file.<br />
<br />
The constructor "Done a" is defined with a label sector: <hask>Done {unpack :: (a,O)}</hask> <br />
is equivalent to <hask>Done (a,O)</hask>. <br />
<br />
The only difference is that, this way, we are also defining a method<br />
to retrieve the pair (a,O) (in our case "O" is a synonymous for<br />
String, whereas "a" is a variable type) from an object of type "Done<br />
a".<br />
<br />
<haskell><br />
<br />
> instance Monad M2 where<br />
> return a = Done (a, "")<br />
> m >>= f = case m of<br />
> Ex e -> Ex e<br />
> Done (a, x) -> case (f a) of<br />
> Ex e1 -> Ex e1<br />
> Done (b, y) -> Done (b, x ++ y)<br />
<br />
</haskell><br />
<br />
Now our binding operations gets more complicated by the fact that we<br />
have to concatenate the output, as we did before, '''and''' check for<br />
exceptions.<br />
<br />
It is not possible to do has we did in the [[The Monadic Way Part I#MonadicEvalE| exception producing evaluator]], <br />
where we could check just for "m" (remember the "m" in the first run<br />
stands for "eval t").<br />
<br />
Since at the end we must return the output produced by the evaluation<br />
of "m" ''concatenated'' with the output produced by the evaluation of<br />
"f a" (where "a" is returned by "m", paired with "x" by "Done"), now<br />
we must check if we '''do have''' an output from "f a" produced by<br />
"Done".<br />
<br />
Indeed, now, "f a" can also produce a value constructed by "Ex", and<br />
this value does not contain the pair as the value produced by "Done".<br />
<br />
So, we evaluate "m": <br />
* if we match a value produced by type constructor "Ex" we return a value produced by type constructor "Ex" whose content is the one we extracted in the matching;<br />
* if we match a value produced by "Done" we match the pair it carries "(a,x)" and we analyze what "f a" returns:<br />
** if "f a" returns a value produced by "Ex" we extract the exception and we return it, constructing a value with "Ex"<br />
** if "f a" returns a value produced by "Done" we return "b" and the concatenated "x" and "y". <br />
<br />
And now the evaluator:<br />
<br />
<haskell><br />
<br />
> raise_IOE :: Exception -> M2 a<br />
> raise_IOE e = Ex e<br />
<br />
</haskell><br />
<br />
This is the function to insert in our monad (M2) an exception: we take<br />
a String and produce a value applying the type constructor for<br />
exception "Ex" to its value.<br />
<br />
<haskell><br />
<br />
> print_IOE :: O -> M2 ()<br />
> print_IOE x = Done ((), x)<br />
<br />
</haskell><br />
<br />
The function to produce output is the very same of the one of the [[The Monadic Way Part I#MonadicEvalIO|output-producing monadic evaluator]].<br />
<br />
<haskell><br />
<br />
> eval_IOE :: Term -> M2 Int<br />
> eval_IOE (Con a) = do print_IOE (formatLine (Con a) a)<br />
> return a<br />
> eval_IOE (Add t u) = do a <- eval_IOE t<br />
> b <- eval_IOE u<br />
> let out = formatLine (Add t u) (a + b)<br />
> print_IOE out<br />
> if (a+b) == 42<br />
> then raise_IOE $ out ++ "The Ultimate Answer Has Been Computed!! Now I'm tired!"<br />
> else return (a + b)<br />
<br />
</haskell><br />
<br />
The evaluator procedure did not change very much from the one of the [[The Monadic Way Part I#MonadicEvalIO|output-producing monadic evaluator]].<br />
<br />
We just added the case analysis to see if the condition for raising an exception is met.<br />
<br />
Running with<br />
<br />
eval_IOE (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2)))<br />
<br />
will produce <br />
<br />
Ex "eval (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2))) <= 42 - <br />
The Ultimate Answer Has Been Computed!! Now I'm tired!"<br />
<br />
Look at the <hask>let</hask> clause within the do-notation. We do not<br />
need to use the "let ... in" construction: since all bound variables<br />
remain bound within a <hask>do</hask> procedure (see [[The Monadic Way Part I#Bind|here]]), <br />
we do not need the "in" to specify "where" the variable "out" will be bound in!<br />
<br />
==We Need A State==<br />
<br />
We will keep on adding complexity to our monadic evaluator and this<br />
time we will add a counter. We just want to count the number of<br />
iterations (the number of times "eval" will be called) needed to<br />
evaluate the expression.<br />
<br />
===The basic evaluator, non monadic, with a counter===<br />
<br />
As before we will start by adding this feature to our [[The Monadic Way Part I#BasicEval|basic evaluator]]. <br />
<br />
A method to count the number of iterations, since the lack of<br />
assignment and destructive updates (such as for i=0;i<10;i++;),<br />
is to add an argument to our function, the initial state, number that<br />
in each call of the function will be increased and passed to the next<br />
function call.<br />
<br />
And so, very simply:<br />
<br />
<haskell><br />
<br />
> -- non monadic<br />
> type St a = State -> (a, State)<br />
> type State = Int<br />
> evalNMS :: Term ->St Int<br />
> evalNMS (Con a) x = (a, x + 1)<br />
> evalNMS (Add t u) x = let (a, y) = evalNMS t x in<br />
> let (b, z) = evalNMS u y in<br />
> (a + b, z +1)<br />
<br />
</haskell><br />
<br />
Now evalNMS takes two arguments: the expression of type Term and an<br />
State (which is a synonymous for Int), and will produce a pair<br />
(a,State), that is to say a pair with a variable type "a" and an Int.<br />
<br />
The operations in the evaluator are very similar to the non monadic [[The Monadic Way Part I#BasivEvalO|output producing evaluator]].<br />
<br />
We are now using the "let ... in" clause, instead of the "where", and we are increasing the counter "z" the comes from the evaluation of the second term, but the basic operation are the same:<br />
* we evaluate "evalNMS t x" where "x" is the initial state, and we match and bind the result in "let (a, y) ... in"<br />
* we evaluate "evalNMS u y", where "y" was bound to the value returned by the previous evaluation, and we match and bind the result in "let (b, z) ... in"<br />
* we return a pair formed by the sum of the result (a+b) and the state z increased by 1. <br />
<br />
Let's try it:<br />
<br />
*TheMonadicWay> evalNMS (Add (Con 10) (Add (Add (Con 20) (Con 10)) (Con 2))) 0<br />
(42,7)<br />
*TheMonadicWay> <br />
<br />
As you see we must pass to "evalNMS"the initial state of our counter: 0.<br />
<br />
Look at the type signature of the function "evalNMS":<br />
<haskell><br />
evalNMS :: Term ->St Int<br />
</haskell><br />
<br />
From this signature you could argue that our function takes only<br />
'''one''' argument. But since our type St is defined with the "type"<br />
keyword, St can be substituted with what comes after the "=" sign. So,<br />
the real type signature of our function is:<br />
<br />
<haskell><br />
evalNMS :: Term -> State -> (Int,State)<br />
</haskell><br />
<br />
<div if="typeNewtype"><br />
Just to refresh your memory:<br />
<br />
<haskell><br />
<br />
> type IamAfunction a = (a -> a)<br />
> newtype IamNotAfunction a = NF (a -> a)<br />
> newtype IamNotAfunctionButYouCanUnPackAndRunMe a = F { unpackAndRun :: (a -> a) }<br />
<br />
> a = \x -> x * x<br />
<br />
> a1 :: IamAfunction Int<br />
> a1 = a<br />
<br />
> a2 :: IamNotAfunction Int<br />
> a2 = NF a<br />
<br />
> a3 :: IamNotAfunctionButYouCanUnPackAndRunMe Int<br />
> a3 = F a<br />
<br />
</haskell><br />
<br />
<br />
*TheMonadicWay> a 4<br />
16<br />
*TheMonadicWay> a1 4<br />
16<br />
*TheMonadicWay> a2 4<br />
<br />
<interactive>:1:0:<br />
The function `a2' is applied to one arguments,<br />
but its type `IamNotAfunction Int' has only 0<br />
In the definition of `it': it = a2 4<br />
*TheMonadicWay> a3 4<br />
<br />
<interactive>:1:0:<br />
The function `a3' is applied to one arguments,<br />
but its type `IamNotAfunctionButYouCanUnPackAndRunMe Int' has only 0<br />
In the definition of `it': it = a3 4<br />
*TheMonadicWay> unpackAndRun a3 4<br />
16<br />
*TheMonadicWay><br />
<br />
This means that "a1" is a partial application hidden by a type<br />
synonymous. <br />
<br />
"a2" and "a3" are not function types. They are types that<br />
have a functional value. <br />
<br />
Moreover, since we defined the type constructor of type<br />
"IamNotAfunctionButYouCanUnPackAndRunMe", F, with a label field, in<br />
that label field we defined a method (a label selector) to "extract"<br />
the function from the type "IamNotAfunctionButYouCanUnPackAndRunMe",<br />
and run it:<br />
<br />
<haskell><br />
unpackAndRun a3 4<br />
</haskell><br />
<br />
And what about "a2"? Is it lost forever?<br />
<br />
Obviously not! We need to write a function that unpacks a type<br />
"IamNotAfunction", using its type constructor NF to match the internal<br />
function:<br />
<br />
<haskell><br />
<br />
> unpackNF :: IamNotAfunction a -> a -> a<br />
> unpackNF (NF f) = f<br />
<br />
</haskell><br />
<br />
and run:<br />
<br />
*TheMonadicWay> unpackNF a2 4<br />
16<br />
*TheMonadicWay> <br />
<br />
As you see, "unpackNF" definition is a partial application: we specify<br />
one argument to get a function that gets another argument.<br />
<br />
A label selector does the same thing.<br />
<br />
Later we will see the importance of this distinction, quite obvious<br />
for haskell gurus, but not for us. Till now.<br />
<br />
===The evaluator, monadic, with a counter, without do-notation===<br />
<br />
<br />
'''(Text to be done yet: just a summary)'''<br />
<br />
The moadic version without do notation.<br />
<br />
<haskell><br />
<br />
> -- monadic<br />
> type MS a = State -> (a, State)<br />
<br />
> mkMS :: a -> MS a<br />
> mkMS a = \x -> (a, x)<br />
<br />
> bindMS :: MS a -> (a -> MS b) -> MS b<br />
> bindMS m f = \x -> <br />
> let (a, y) = m x in<br />
> let (b, z) = f a y in<br />
> (b, z)<br />
<br />
> combineMS :: MS a -> MS b -> MS b<br />
> combineMS m f = m `bindMS` \_ -> f<br />
<br />
> incState :: MS ()<br />
> incState = \s -> ((), s + 1)<br />
<br />
> evalMS :: Term -> MS Int<br />
> evalMS (Con a) = incState `combineMS` mkMS a<br />
> evalMS (Add t u) = evalMS t `bindMS` \a -><br />
> evalMS u `bindMS` \b -><br />
> incState `combineMS` mkMS (a + b)<br />
<br />
> --evalMS (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12)))) 0<br />
<br />
</haskell><br />
<br />
===The evaluator, monadic, with counter and output, without do-notation===<br />
<br />
Now we'll add Output to the stateful evaluator:<br />
<br />
<haskell><br />
<br />
> -- state and output<br />
<br />
> type MSO a = State -> (a, State, Output)<br />
<br />
> mkMSO :: a -> MSO a<br />
> mkMSO a = \s -> (a, s, "")<br />
<br />
> bindMSO :: MSO a -> (a -> MSO b) -> MSO b<br />
> bindMSO m f = \x -> <br />
> let (a, y, s1) = m x in<br />
> let (b, z, s2) = f a y in<br />
> (b, z, s1 ++ s2)<br />
<br />
> combineMSO :: MSO a -> MSO b -> MSO b<br />
> combineMSO m f = m `bindMSO` \_ -> f<br />
<br />
> incMSOstate :: MSO ()<br />
> incMSOstate = \s -> ((), s + 1, "")<br />
<br />
> outMSO :: Output -> MSO ()<br />
> outMSO = \x s -> ((),s, x)<br />
<br />
> evalMSO :: Term -> MSO Int<br />
> evalMSO (Con a) = incMSOstate `combineMSO` <br />
> outMSO (formatLine (Con a) a) `combineMSO` <br />
> mkMSO a<br />
> evalMSO (Add t u) = evalMSO t `bindMSO` \a -><br />
> evalMSO u `bindMSO` \b -><br />
> incMSOstate `combineMSO` <br />
> outMSO (formatLine (Add t u) (a + b)) `combineMSO`<br />
> mkMSO (a + b)<br />
<br />
> --evalMSO (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12)))) 0<br />
<br />
</haskell><br />
<br />
===The monadic evaluator with output and counter in do-notation=== <br />
<br />
State, Output in do-notation. Look at how much the complexity of our<br />
(>>=) founction is increasing:<br />
<br />
<haskell><br />
<br />
> -- thanks to Brian Hulley<br />
<br />
> newtype MSIO a = MSIO (State -> (a, State, Output))<br />
> instance Monad MSIO where<br />
> return a = MSIO (\s -> (a, s, ""))<br />
> (MSIO m) >>= f = MSIO $ \x -><br />
> let (a, y, s1) = m x in<br />
> let MSIO runNextStep = f a in<br />
> let (b, z, s2) = runNextStep y in<br />
> (b, z, s1 ++ s2)<br />
<br />
<br />
> incMSOIstate :: MSIO ()<br />
> incMSOIstate = MSIO (\s -> ((), s + 1, ""))<br />
<br />
> print_MSOI :: Output -> MSIO ()<br />
> print_MSOI x = MSIO (\s -> ((),s, x))<br />
<br />
> eval_MSOI :: Term -> MSIO Int<br />
> eval_MSOI (Con a) = do incMSOIstate<br />
> print_MSOI (formatLine (Con a) a)<br />
> return a<br />
<br />
> eval_MSOI (Add t u) = do a <- eval_MSOI t<br />
> b <- eval_MSOI u<br />
> incMSOIstate<br />
> print_MSOI (formatLine (Add t u) (a + b))<br />
> return (a + b)<br />
<br />
> run_MSOI :: MSIO a -> State -> (a, State, Output)<br />
> run_MSOI (MSIO f) s = f s<br />
<br />
> --run_MSOI (eval_MSOI (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12))))) 0<br />
<br />
</haskell><br />
<br />
===Another version of the monadic evaluator with output and counter, in do-notation===<br />
<br />
This is e second version that exploit label fields in datatype to<br />
decrease the complexity of the binding operations.<br />
<br />
<haskell><br />
<br />
> -- Thanks Udo Stenzel<br />
<br />
> newtype Eval_SIO a = Eval_SIO { unPackMSIOandRun :: State -> (a, State, Output) }<br />
> instance Monad Eval_SIO where<br />
> return a = Eval_SIO (\s -> (a, s, ""))<br />
> (>>=) m f = Eval_SIO (\x -><br />
> let (a, y, s1) = unPackMSIOandRun m x in<br />
> let (b, z, s2) = unPackMSIOandRun (f a) y in<br />
> (b, z, s1 ++ s2))<br />
<br />
> incSIOstate :: Eval_SIO ()<br />
> incSIOstate = Eval_SIO (\s -> ((), s + 1, ""))<br />
<br />
> print_SIO :: Output -> Eval_SIO ()<br />
> print_SIO x = Eval_SIO (\s -> ((),s, x))<br />
<br />
> eval_SIO :: Term -> Eval_SIO Int<br />
> eval_SIO (Con a) = do incSIOstate<br />
> print_SIO (formatLine (Con a) a)<br />
> return a<br />
> eval_SIO (Add t u) = do a <- eval_SIO t<br />
> b <- eval_SIO u<br />
> incSIOstate<br />
> print_SIO (formatLine (Add t u) (a + b))<br />
> return (a + b)<br />
<br />
> --unPackMSIOandRun (eval_SIO (Add (Con 6) (Add (Con 16) (Add (Con 20) (Con 12))))) 0<br />
<br />
</haskell><br />
<br />
<br />
==If There's A State We Need Some Discipline: Dealing With Complexity==<br />
<br />
In order to increase the complexity of our monad now we will try to<br />
mix State (counter), Exceptions and Output.<br />
<br />
This is an email [http://www.haskell.org/pipermail/haskell-cafe/2006-August/017672.html I send to the haskell-cafe mailing list]:<br />
<br />
<pre><br />
Now I'm trying to create a statefull evaluator, with output and<br />
exception, but I'm facing a problem I seem not to be able to<br />
conceptually solve.<br />
<br />
Take the code below.<br />
Now, in order to get it run (and try to debug) the Eval_SOI type has a<br />
Raise constructor that produces the same type of SOIE. Suppose instead it<br />
should be constructing something like Raise "something". <br />
Moreover, I wrote a second version of >>=, commented out.<br />
This is just to help me illustrate to problem I'm facing.<br />
<br />
Now, >>= is suppose to return Raise if "m" is matched against Raise<br />
(second version commented out).<br />
If "m" matches SOIE it must return a SOIE only if "f a" does not<br />
returns a Raise (output must be concatenated).<br />
<br />
I seem not to be able to find a way out. Moreover, I cannot understand<br />
if a way out can be possibly found. Something suggests me it could be<br />
related to that Raise "something".<br />
But my feeling is that functional programming could be something out<br />
of the reach of my mind... by the way, I teach Law, so perhaps you'll<br />
forgive me...;-)<br />
<br />
If you can help me to understand this problem all I can promise is<br />
that I'll mention your help in the tutorial I'm trying to write on<br />
"the monadic way"... that seems to lead me nowhere.<br />
<br />
Thanks for your kind attention.<br />
<br />
Andrea<br />
</pre><br />
<br />
This was the code:<br />
<br />
<haskell><br />
data Eval_SOI a = Raise { unPackMSOIandRun :: State -> (a, State, Output) }<br />
| SOIE { unPackMSOIandRun :: State -> (a, State, Output) }<br />
<br />
instance Monad Eval_SOI where<br />
return a = SOIE (\s -> (a, s, ""))<br />
m >>= f = SOIE (\x -><br />
let (a, y, s1) = unPackMSOIandRun m x in<br />
case f a of<br />
SOIE nextRun -> let (b, z, s2) = nextRun y in <br />
(b, z, s1 ++ s2)<br />
Raise e1 -> e1 y --only this happens<br />
<br />
)<br />
-- (>>=) m f = case m of<br />
-- Raise e -> error "ciao" -- why this is not going to happen?<br />
-- SOIE a -> SOIE (\x -><br />
-- let (a, y, s1) = unPackMSOIandRun m x in<br />
-- let (b, z, s2) = unPackMSOIandRun (f a) y in <br />
-- (b, z, s1 ++ s2)) <br />
<br />
<br />
incSOIstate :: Eval_SOI ()<br />
incSOIstate = SOIE (\s -> ((), s + 1, ""))<br />
<br />
print_SOI :: Output -> Eval_SOI ()<br />
print_SOI x = SOIE (\s -> ((),s, x))<br />
<br />
raise x e = Raise (\s -> (x,s,e))<br />
<br />
eval_SOI :: Term -> Eval_SOI Int<br />
eval_SOI (Con a) = do incSOIstate<br />
print_SOI (formatLine (Con a) a)<br />
return a<br />
eval_SOI (Add t u) = do a <- eval_SOI t<br />
b <- eval_SOI u<br />
incSOIstate<br />
print_SOI (formatLine (Add t u) (a + b))<br />
if (a + b) == 42 <br />
then raise (a+b) " = The Ultimate Answer!!"<br />
else return (a + b)<br />
<br />
runEval exp = case eval_SOI exp of<br />
Raise a -> a 0<br />
SOIE p -> let (result, state, output) = p 0 in<br />
(result,state,output)<br />
<br />
<br />
<br />
--runEval (Add (Con 10) (Add (Con 28) (Add (Con 40) (Con 2))))<br />
</haskell><br />
<br />
This code will produce <br />
<br />
eval (Con 10) <= 10 -<br />
eval (Con 28) <= 28 -<br />
eval (Con 40) <= 40 -<br />
eval (Con 2) <= 2 - = The Ultimate Answer!!<br />
eval (Add (Con 28) (Add (Con 40) (Con 2))) <= 70 -<br />
eval (Add (Con 10) (Add (Con 28) (Add (Con 40) (Con 2)))) <= 80 -<br />
<br />
The exception appears in the output, but executioon is not stopped.<br />
<br />
===Monadic evaluator with output, counter and exception, in do-notation===<br />
<br />
Brian Hulley [http://www.haskell.org/pipermail/haskell-cafe/2006-August/017680.html came up with this solution]:<br />
<br />
<haskell><br />
<br />
> -- thanks to Brian Hulley<br />
> data Result a<br />
> = Good a State Output<br />
> | Bad State Output Exception<br />
> deriving Show<br />
<br />
> newtype Eval_SIOE a = SIOE {runSIOE :: State -> Result a}<br />
<br />
> instance Monad Eval_SIOE where<br />
> return a = SIOE (\s -> Good a s "")<br />
> m >>= f = SIOE $ \x -><br />
> case runSIOE m x of<br />
> Good a y o1 -><br />
> case runSIOE (f a) y of<br />
> Good b z o2 -> Good b z (o1 ++ o2)<br />
> Bad z o2 e -> Bad z (o1 ++ o2) e<br />
> Bad z o2 e -> Bad z o2 e<br />
<br />
> raise_SIOE e = SIOE (\s -> Bad s "" e)<br />
<br />
> incSIOEstate :: Eval_SIOE ()<br />
> incSIOEstate = SIOE (\s -> Good () (s + 1) "")<br />
<br />
> print_SIOE :: Output -> Eval_SIOE ()<br />
> print_SIOE x = SIOE (\s -> Good () s x)<br />
<br />
<br />
> eval_SIOE :: Term -> Eval_SIOE Int<br />
> eval_SIOE (Con a) = do incSIOEstate<br />
> print_SIOE (formatLine (Con a) a)<br />
> return a<br />
> eval_SIOE (Add t u) = do a <- eval_SIOE t<br />
> b <- eval_SIOE u<br />
> incSIOEstate<br />
> let out = formatLine (Add t u) (a + b)<br />
> print_SIOE out<br />
> if (a+b) == 42<br />
> then raise_SIOE $ out ++ "The Ultimate Answer Has Been Computed!! Now I'm tired!"<br />
> else return (a + b)<br />
<br />
> runEval exp = case runSIOE (eval_SIOE exp) 0 of<br />
> Bad s o e -> "Error at iteration n. " ++ show s ++ <br />
> " - Output stack = " ++ o ++ <br />
> " - Exception = " ++ e<br />
> Good a s o -> "Result = " ++ show a ++ <br />
> " - Iterations = " ++ show s ++ " - Output = " ++ o<br />
<br />
</haskell><br />
<br />
Run with runEval (Add (Con 18) (Add (Con 12) (Add (Con 10) (Con 2))))<br />
<br />
==Suggested Readings==<br />
<br />
Cale Gibbard, [http://haskell.org/haskellwiki/Monads_as_Containers Monads as Containers]<br />
<br />
Jeff Newbern, [http://www.nomaware.com/monads/html/index.html All About Monads]<br />
<br />
[http://haskell.org/haskellwiki/IO_inside IO Inside]<br />
<br />
[http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html You Could Have Invented Monads! (And Maybe You Already Have.) by sigfpe]<br />
<br />
<br />
==Acknowledgments==<br />
<br />
Thanks to Neil Mitchell, Daniel Fisher, Bulat Ziganzhin, Brian Hulley<br />
and Udo Stenzel for the invaluable help they gave, in the<br />
[http://www.haskell.org/mailman/listinfo/haskell-cafe haskell-cafe mailing list], <br />
in understanding this topic.<br />
<br />
I couldn't do it without their help.<br />
<br />
Obviously errors are totally mine. But this is a wiki so, please,<br />
correct them!<br />
<br />
- [[User:AndreaRossato|Andrea Rossato]]</div>Fishttps://wiki.haskell.org/index.php?title=FilePath&diff=5458FilePath2006-08-17T07:46:32Z<p>Fis: </p>
<hr />
<div>I have written a System.FilePath module in part based on the one in<br />
Yhc, and in part based on the one in Cabal (thanks to Lemmih). The aim<br />
is to try and get this module into the base package, as FilePath's are<br />
something many programs use, but its all too easy to hack up a little<br />
function that gets it right most of the time on most platforms, and<br />
there lies a source of bugs.<br />
<br />
This module is Posix (Linux) and Windows capable - just import<br />
System.FilePath and it will pick the right one. Of course, if you<br />
demand Windows paths on all OS's, then System.FilePath.Windows will<br />
give you that (same with Posix). Written in Haskell 98 + Hierarchical<br />
Modules.<br />
<br />
* Homepage: http://www-users.cs.york.ac.uk/~ndm/projects/libraries.php<br />
* Haddock: http://www-users.cs.york.ac.uk/~ndm/projects/filepath/System-FilePath.html<br />
* Darcs: darcs get http://www.cs.york.ac.uk/fp/darcs/filepath<br />
* Source: http://www.cs.york.ac.uk/fp/darcs/filepath/System/FilePath.hs<br />
* Readme: http://www.cs.york.ac.uk/fp/darcs/filepath/readme.txt<br />
<br />
If you go to the haddock page there are a few little examples at the<br />
top of the file.<br />
<br />
The Yhc project, hquickfile and a few other utilites are already using<br />
this module succesfully.<br />
<br />
Comments welcome. Thanks<br />
<br />
== Thoughts/Todo ==<br />
<br />
For that there would need to<br />
be some FilePath function such as checkDownstream :: FilePath -><br />
FilePath -> Bool which checks if some path is below another in the<br />
tree. I'll think about adding that one. This function needs to be seriously robust!<br />
<br />
<br />
> I haven't been following this discussion very closely, but this caught my eye.<br />
> Has anyone pointed out yet that eliminating ".." in a FilePath isn't valid in<br />
> the presence of symbolic links? I vaguely recall that this is why Krasimir's<br />
> System.FilePath library doesn't include normalisation. Normalisation that just<br />
> changes separators, removes redundant separators and removes "." components is<br />
> probably ok.<br />
Ok, I'll remove this behaviour<br />
<br />
<br />
> I don't really see the point of fullPathWith. Isn't it just combine?<br />
It also applies normalise to the result, although I'm not sure thats a<br />
particularly useful thing to do. I'll think about this.<br />
<br />
<br />
> I think shortPath is on dodgy ground, given the difficulty with normalising<br />
> FilePaths, and the fact that paths are not unique in the presence of symlinks.<br />
I think this is still a useful thing, but I'll think harder about it<br />
in relation to symlinks, and figure out what properties it should<br />
have.<br />
<br />
<br />
> The temporary file stuff is wrong - see System.IO.openTemporaryFile. The only<br />
> way to reliably create a temporary file is to open it at the same time,<br />
> otherwise there's a race condition.<br />
Looking at it again, I'm not sure that the temporary operations belong<br />
in this module. Ditto for the directory operations. It would be handy<br />
if the directory operations (particularly ensureDirectory) were<br />
somewhere else in the standard libraries though.<br />
<br />
== Thoughts on FilePath as a abstract type ==<br />
<br />
Add them here :)</div>Fishttps://wiki.haskell.org/index.php?title=Haskell&diff=2348Haskell2006-02-17T08:59:14Z<p>Fis: </p>
<hr />
<div>[[image:haskelllogo.jpg|center|Haskell &ndash; A purely functional language]]<br />
<br />
Haskell is a general purpose, purely functional programming language. Haskell compilers are freely available for almost any computer. <br />
<br />
__NOTOC__<br />
<br />
<center><br />
[[Special:Allpages|All Pages]] - [[Special:Categories|Categories]] - [[HaskellWiki:Community Portal|Community Portal]]<br/><br />
[[:Category:Language|Language]] |<br />
[[:Category:Packages|Packages]] |<br />
[[:Category:Standard libraries|Standard libraries]] |<br />
[[:Category:Idioms|Idioms]] |<br />
[[:Category:Tools|Tools]] |<br />
[[:Category:Proposals|Proposals]]<br />
</center><br />
<br />
<br />
== About Haskell ==<br />
<br />
* [[Introduction|A Short Introduction to Haskell]]<br />
* [[Definition|Definition of the Language and the Standard Libraries]]<br />
* [http://www.haskell.org/haskell-history.html History of Haskell]<br />
* [[Applications|Applications Written in Haskell]]<br />
* [[Education|Haskell in Education]]<br />
* [[Future|The Future of Haskell]]<br />
<br />
== Learning Haskell ==<br />
<br />
* [[Books and tutorials|Books and Tutorials about Programming in Haskell]]<br />
* [http://haskell.org/learning.html Learning Haskell]<br />
* [[By topic|Haskell by topic]]<br />
<br />
== Using Haskell ==<br />
<br />
* [[Implementations|Haskell Compilers and Interpreters]]<br />
* [[Projects|Libraries and Tools for Haskell]]<br />
* Old [http://haskell.org/hawiki/ HaWiki: Questions & Answers] (content to be integrated here)<br />
<br />
== The Community ==<br />
<br />
* [[Mailing Lists]]<br />
* [http://haskell.org/communities/ Communities and their Projects (latest report: November 2005)]<br />
* [[Links to People and Further Pages]]<br />
* [[Jobs]]<br />
* [[Consultants|Haskell Consultants]]<br />
* [[Humor|Haskell Humor]]<br />
* [[Merchandise]]<br />
<br />
== [[News]] ==<br />
{{:News}}<br />
== [[Events]] ==<br />
{{:Events}}</div>Fishttps://wiki.haskell.org/index.php?title=By_topic&diff=2347By topic2006-02-17T08:59:03Z<p>Fis: </p>
<hr />
<div>This is a collection of material on the Haskell programming language, ordered by topics.<br />
<br />
== Strictness ==<br />
<br />
Amanda Clare has written a paper on various methods for twisting the evaluation order: http://users.aber.ac.uk/afc/stricthaskell.html.</div>Fis