Haskell

From Ggl's wiki

Contents 1 What is Haskell 1.1 Features 1.2 Functions 1.3 Lists 1.4 Functional Programming 1.4.1 Papers to read 1.4.2 Books 1.4.3 Concepts 1.5 Tools 1.6 Short Examples 1.6.1 Group a list of tuples by keys 2 Sample Programs 2.1 Fastcgi configuration 2.2 Feeds fetcher 2.3 Del.icio.us example 2.4 Control.Applicative 2.5 Using the Maybe monad 3 Tips 3.1 Uncurry

What is Haskell

Features

Haskell is a pure functional programming language. Its main features are:

• purity (no side-effects)
• high-order functions
• lazy evaluation: a expression is evaluated only when needed
• strongly typed with type inference
• polymorphism
• currying
• pattern matching
• list comprehension
• monads
• type classes
• layout parsing: code blocks can be delimited by the layout (tab spaces)

Functions

composition: rotate = flipV . flipH forward composition: rotate = flipH >.> flipV

lambda: \x y = y*y

partial application:

sum x y = x + y
sum 1 -> 1 + y

Lists

(head:tail) commonly written (x:xs)

List comprehension: [y | y <- xs, y <= x]

Useful functions: map, filter, foldr1, foldr, zip, zipWith

Functional Programming

Papers to read

• Why functional Programming Matters? by John Hughes
• The Typeclassopedia by Brent Yorgey
• Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire by Eirik Meijer, Maarten Fokkinga, and Ross Paterson
• Lectures on Functional Programming from the Chalmer University. Also reference essential papers to read.
• How to Write a Financial Contract by Simon Peyton Jones explains how to write a combinator library (embedded DSL) for composing contracts
• The Design of a Pretty-printing Library by John Hughes
• Monadic Parser Combinators by Graham Hutton and Eirik Meijer
• Functional Pearls by many great people

Books

• Real World Haskell by Bryan O'Sullivan, Don Stewart, and John Goerzen is really a great resource
• The Haskell School of Expression by Paul Hudak has nice chapters about embedded DSL design

Concepts

• Understand the difference between strict and lazy evaluation
• Try to use Data.ByteString instead of String
• Prelude and Data.List
• Learn how to use map, concatMap, foldl, foldl', foldr, zip, zipWith
• Types to handle errors Data.Maybe and Data.Either
• Understand what deriving (Eq, Show) means
• Convenient operators and functions like ($), (.), flip
• Control.Applicative
• Data.Functor
• Data.Monoid
• Learn to use monads Control.Monad without the do notation. See the description on haskell.org Wiki and a Tour of the Haskell Monad Functions
• MonadPlus
• Monad Transformers
• For interleaved IO and parsing, try Iteratee/Enumeratee/Enumerator and the module enumerator available on Hackage
• Data.Map

Tools

• HLint
• Cabal

Short Examples

Group a list of tuples by keys

> import Data.List
> let l = [('a',1),('d',4),('b',2),('c',3),('c',5),('x',3),('x',7)]
> map (\x -> (fst $ head x, snd $ unzip x)) $ groupBy (\(x1, y1) (x2, y2) -> x1 == x2)
[('a',[1]),('d',[4]),('b',[2]),('c',[3,5]),('x',[3,7])]
> import Data.Map
> let m = Data.Map.fromList $ Data.List.map (\x -> (fst $ head x, snd $ unzip x)) $ groupBy (\(x1, y1) (x2, y2) -> x1 == x2) rsl
> m ! 'a'
[1]
> m ! 'c'
[3,5]

Some examples could be find there.

module Main where
import System.IO
import Char

Define some custom types. Simple types:

type Person = String
type Book = String

List [] of (,) tuples (here pairs):

type LoanDB = [(Person, Book)]

Define the function that build the exemple database list:

exampleDB :: LoanDB
exampleDB = [("Alice", "Tintin"),
             ("Anna", "Little Women"),
             ("Alice", "Asterix"),
             ("Rory", "Tintin")]

Retrieve books from LoadDB db that were loaned by Person borrower. It uses a list comprehension where a book is in the returned list, if the person in the tuple (person, book) from db is the borrower:

books :: LoanDB -> Person -> [Book]
books db borrower
    = [ book | (person, book) <- db, person==borrower]

Prepend the tuple (borrower, book) to db. ++ is the concatenation operator.

makeLoan :: LoanDB -> Person -> Book -> LoanDB
makeLoan db borrower book
   = [(borrower, book)] ++ db

Remove (borrower, book) from db. Actually, it uses a list comprehension to return a list where all but (borrower, book) tuples are.

returnLoan :: LoanDB -> Person -> Book -> LoanDB
returnLoan db borrower book
   = [(bwer, bk) | (bwer, bk) <- db, (bwer, bk) /= (borrower, book)]

Return a list of people who borrowed book:

borrowers :: LoanDB -> Book -> [Person]
borrowers db book
    = [borrower | (borrower, bk) <- db, bk==book]

Tell if book was borrowed. Return True is there is at least one borrower e.g. length(borrowers db book) > 0.

borrowed :: LoanDB -> Book -> Bool
borrowed db book
    = if length(borrowers db book) > 0
        then True
        else False

How many books did borrower borrow:

numBorrowed :: LoanDB -> Person -> Int
numBorrowed db borrower
    = length(books db borrower)

In a list (x:xs), x is the head and xs the tail. It's often used in list recursion.

Pattern matching:

sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs

firstDigit st
    = case (digits st) of
        [] ->'\O'
        (x:_) -> X

Guards:

comparison x y 
       | x < y = "The first is less"
       | x > y = "The second is less"
       | otherwise = "They are equal"

Insertion in an ordered list:

ins :: Int -> [Int] -> [Int]
ins x [] = [x]
ins x (y:ys) =
  | x <= y = x:(y:ys)
  | otherwise = y : ins x ys

Quicksort:

qSort :: [Int] -> [Int]
qSort [] = []
qSort (x:xs)
   = qSort [y | y <- xs, y <= x] ++ [x] ++ qSort [y | y <- xs, y > x]

Sample Programs

Fastcgi configuration

With nginx, add this to your /etc/nginx/sites-enabled/<vhost> (might be in /etc/nginx/sites-enabled/default):

server {
         listen 80;
         [...]
         location /hs {
            include fastcgi_params;
            fastcgi_pass localhost:9000;
            fastcgi_index index.hs;
         }
         [...]
}

You should also have the file /etc/nginx/fastcgi_params (by default in debian package) with these values:

fastcgi_param  QUERY_STRING       $query_string;
fastcgi_param  REQUEST_METHOD     $request_method;
fastcgi_param  CONTENT_TYPE       $content_type;
fastcgi_param  CONTENT_LENGTH     $content_length; 

fastcgi_param  SCRIPT_NAME        $fastcgi_script_name;
fastcgi_param  REQUEST_URI        $request_uri;
fastcgi_param  DOCUMENT_URI       $document_uri;
fastcgi_param  DOCUMENT_ROOT      $document_root;
fastcgi_param  SERVER_PROTOCOL    $server_protocol;

fastcgi_param  GATEWAY_INTERFACE  CGI/1.1;
fastcgi_param  SERVER_SOFTWARE    nginx/$nginx_version;

fastcgi_param  REMOTE_ADDR        $remote_addr;
fastcgi_param  REMOTE_PORT        $remote_port;
fastcgi_param  SERVER_ADDR        $server_addr;
fastcgi_param  SERVER_PORT        $server_port;
fastcgi_param  SERVER_NAME        $server_name;

Then when you go to http://localhost/hs/index.hs the fastcgi handler will connect to the fastcgi process on tcp port 9000. The fastcgi process may listen to a unix socket for better performance.

Feeds fetcher

module Main where

import Control.Applicative ((<*>))
import System.Environment ( getArgs )
import Data.List ( sortBy )
import Data.Ord ( comparing )
import Data.Maybe ( fromJust )
import Network.URI ( parseURI )
import Network.HTTP.Base
import Network.HTTP ( Request, simpleHTTP, rspBody )
import Text.Feed.Types ( Feed, Item )
import Text.Feed.Import
import Text.Feed.Query
import System.Locale ( defaultTimeLocale )
import System.Time ( formatCalendarTime )
import System.Time.Parse ( parseCalendarTime )

-- |A configuration has the format: "uri [name]"
parseConfigLine :: String -> (String, String)
parseConfigLine l = (uri l, name l)
    where
        uri = takeWhile (/= ' ')
        name = takeWhile (/= ']') . tail . dropWhile (/= '[')

parseConfigString :: String -> [(String, String)]
parseConfigString = map parseConfigLine . lines

parseConfigPath :: FilePath -> IO [(String, String)]
parseConfigPath = fmap parseConfigString . readFile

getFeed :: (String, String) -> IO Feed
getFeed (uri, name) =
    simpleHTTP (Request uri' GET [] "") >>= \(Right x) ->
        return . fromJust . parseFeedString $ rspBody x
    where
        Just uri' = parseURI uri

getFeeds :: [(String, String)] -> IO [Feed]
getFeeds = mapM getFeed

itemTitle = fromJust . getItemTitle
itemDate = fromJust . getItemDate
itemLink = fromJust . getItemLink

-- "Wed, 9 Dec 2009 16:49:31 +0000"
dateFormat = "%a, %d %b %Y %H:%M:%S %Z"
convertDate = fromJust . parseCalendarTime defaultTimeLocale dateFormat
-- "2009/12/09 16:49 UTC"
showDate = formatCalendarTime defaultTimeLocale "%Y/%m/%d %R %Z"

itemFormat "date" item  = Just $  showDate $ convertDate $ itemDate item
itemFormat "uri" item   = Just $ concat ["\tURI: ", itemLink item]
itemFormat _ item = Nothing

showItem :: (Item, String) -> [String] -> String
showItem (i, ft) fmt = concat $ (["[" ++ ft ++ "- "]) ++
        (map (\x -> case itemFormat x i of
                Nothing -> ""
                Just f -> f) fmt) ++ ["] "] ++ [itemTitle i]

main :: IO ()
main = do
    feeds <- getArgs >>= parseConfigPath . head >>= getFeeds
    let items_sorted = sortBy (\(i1, _) (i2, _) ->
            comparing (convertDate . itemDate) i1 i2) (items feeds)
    putStrLn $ unlines $ map (flip showItem ["date"]) $ items_sorted
    where
        items = concatMap (\x ->
                map (\y -> (y, getFeedTitle x)) (getFeedItems x))

with http-enumerator:

import Data.Maybe
import Network.HTTP.Enumerator
import qualified  Data.ByteString.Lazy as L
import Data.ByteString.Lazy.Char8
import Text.Feed.Import
import Text.Feed.Query

rss <- simpleHttp "http://twitter.com/favorites/20685772.rss"
let maybefeed = parseFeedString (unpack rss)
let feed = fromJust maybefeed
rssTitle feed
Prelude.putStrLn . Prelude.unlines $  Prelude.map (fromJust . getItemTitle) $ getFeedItems feed

Del.icio.us example

A simple example of haskell delicious module usage to retrieve the last 10 links.

import Network.Delicious

user = User { userName = "user", userPass = "password" }
posts = withUser user (getAll Nothing)
posts' <- runDM user posts
take 10 . map postDesc $ posts'

Control.Applicative

The paper that inspired it Applicative Programming with Effects by Conor McBride and Ross Paterson. in Journal of Functional Programming 18:1 (2008), pages 1-13.

Please find the reference documentation on Hackage.

Control.Applicative provides lifting and sequencing operators. It “describes a structure intermediate between a functor and a monad: it provides pure expressions and sequencing, but no binding.”.

Applicative functors:

class Functor f => Applicative f where

• pure
• <*>
• *>
• <*

An Applicative must (constraint in the type class definition) also be a Functor.

Alternatives:

class Applicative f => Alternative f where

• empty
• <|>
• some
• many

Utility functions:

• <$> (fmap)
• <$
• <**> (<*> with reversed arguments
• liftA, liftA2, liftA3
• optional (one or none)

Example in Attoparsec from RFC2616.hs:

response :: Parser (Response, [Header])
response = (,) <$> responseLine <*> many messageHeader <* endOfLine

(,) is the construtor for the tuple type:

> :t (,)
(,) :: a -> b -> (a, b)
> (,) 1 2
(1,2)

And then we have three infix operators:

> :info (<$>)
(<$>) :: (Functor f) => (a -> b) -> f a -> f b
        -- Defined in Data.Functor
infixl 4 <$>
> :info (<*>)
class (Functor f) => Applicative f where
  ...
  (<*>) :: f (a -> b) -> f a -> f b
  ...
        -- Defined in Control.Applicative
infixl 4 <*>
> :info (<*)
class (Functor f) => Applicative f where
  ...
  (<*) :: f a -> f b -> f a
        -- Defined in Control.Applicative
infixl 4 <*

infixl means infix with left associativity. The operator is applied from left to right. They all have the same precedence that equals 4, so it begins with <$>. It applies the constructor (,) to the right operand of <$>: responseLine <*> many messageHeader <* endOfLine.

<*> sequences application. It first applies its left operand and then its right operand. ResponseLine has the following signature:

responseLine :: Parser Response

Response is a constructor i.e. it has the type a -> b. The first argument of the following <*> has the type f (a -> b). Now we can tell that it is actually Parser Response. Once responseLine is applied, <*> applies many messageHeader <* endOfLine.

many messageHeader will be evaluated first, and finally <* applies endOfLine and returns the result of its left operand many messageHeader.

Using the Maybe monad

A example of how to use Maybe as a monad to avoid nested case of constructs:

cookieRequest :: Request -> IO Request
cookieRequest request = do
    return $ case lookup "Cookie" $ requestHeaders request of
        Nothing         -> request
        Just cookieStr  -> do
            case parseCookie cookieStr of
                Nothing         -> request
                Just cookies    -> do
                    let cookieHeaders = P.map fromCookie cookies
                    request {requestHeaders = cookieHeaders ++ requestHeaders request}
                    where
                        cookieHeaderName name = mkCIByteString $ BS.concat ["cookie.", name]
                        fromCookie c = (cookieHeaderName $ cookieName c, cookieValue c)

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

    (Just _) >>  k      = k
    Nothing  >>  _      = Nothing

    return              = Just
    fail _              = Nothing

cookieRequest :: Request -> IO Request
cookieRequest request = return $ fromMaybe request $
    Just request >>= lookup "Cookie" . requestHeaders >>= parseCookie >>= \cookies ->
        return $ request {requestHeaders = cookieHeaders cookies ++ requestHeaders request}
        where
            cookieHeaders cookies = P.map fromCookie cookies
            cookieHeaderName name = mkCIByteString $ BS.concat ["cookie.", name]
            fromCookie c = (cookieHeaderName $ cookieName c, cookieValue c)

It implicitly means a error returns Nothing. Then we only show computations for successful results. I find that this form clearly shows we take the request, lookup the "Cookie" header, then parse the cookie and use the result to update request headers.

Tips

Uncurry

uncurry :: (a -> b -> c) -> (a, b) -> c