Haskell/概述

Haskell 是一種標準化的函數語言程式設計語言，具有 非嚴格 語義。Haskell 的功能包括支援遞迴函式、資料型別、模式匹配和列表推導。透過組合這些功能，在程序式程式設計語言中難以編寫的函式在 Haskell 中幾乎可以輕鬆實現。該語言是截至 2011 年，進行最多研究的函式式語言。

以下示例展示了 Haskell 的一些特性，面向熟悉其他程式語言的使用者。

示例

階乘 函式的經典定義

fac 0 = 1 
fac n = n * fac (n - 1)

使用 Haskell 的內建列表表示法和標準 product 函式的簡明定義

fac n = product [1..n]

以上兩個定義都應該透過使用等式推理的智慧編譯器編譯成相同的有效程式碼。

返回斐波那契數列中第 n 個數的函式的樸素實現

fib 0 = 0
fib 1 = 1 
fib n = fib (n - 2) + fib (n - 1)

返回斐波那契數列的線性時間列表的函式

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

前面的函式定義了一個無限列表，這得益於惰性求值。

可以將 fib 實現為

fib n = fibs !! n

(!! 是一個運算子，它獲取列表中的第 n 個元素)。

快速排序演算法可以在 Haskell 中簡潔地表達為

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

(請注意，按照慣例，快速排序在記憶體中交換值；但是，由於 Haskell 的列表是不可變的，因此需要複製值來代替)。

非跳躍穩定歸併排序是

mgsort less [] = []
mgsort less xs = head $ until (null.tail) pairs [[x] | x <- xs]
    where 
      pairs (x:y:xs)    = merge x y : pairs xs
      pairs xs          = xs
      merge (x:xs) (y:ys)
            | less y x  = y : merge (x:xs) ys 
            | True      = x : merge  xs (y:ys)
      merge  xs     ys  = xs ++ ys

其中 (.) 是函式組合運算子 (h . g) x = h (g x) ，(\x -> ...) 是一個 lambda 表示式（一個無名函式），預定義函式  until cond fun  重複應用一個函式 fun  直到滿足條件 cond  ；使用 where 關鍵字引入區域性定義，展示了模式的使用（使用 (x:xs) 匹配一個非空列表，其頭部為 x，尾部為 xs）和保護。

哈明數序列只是

hamm = 1 : map (2*) hamm `union` 
              (map (3*) hamm `union` map (5*) hamm)
-- a union of two ordered lists:
union (x:xs) (y:ys) = case (compare x y) of
          LT -> x : union  xs  (y:ys)
          EQ -> x : union  xs     ys 
          GT -> y : union (x:xs)  ys

使用節（部分應用運算子）和內建函式 map 處理列表，無論是有限的還是無限的，這得益於惰性（即按需）求值。此外，將函式名括在反引號中會將其轉換為中綴運算子，以便子表示式會自動形成，就像透過適當放置括號一樣，形成巢狀表示式，就像在 2+3+5 --> ((2+3)+5) ；註釋行由兩個破折號引入。

最後，透過試除得到的素數的無限列表是

primes = 2 : sieve [3..] primes   -- 2 : _Y ((3:) . sieve [5,7..])
             where
             sieve xs (p:ps) | (h,t) <- span (< p*p) xs =
                                h ++ sieve [n | n <- t, rem n p > 0] ps

或者作為具有有序列表的無界增量埃拉託斯特尼篩法，

import Data.List.Ordered

primes = 2 : _Y ((3:) . minus [5,7..]   -- ps = [2..] \\ [[p*p, p*p+p..] | p <- ps]
                      . unionAll 
                      . map (\p -> [p*p, p*p+2*p..]))
  
_Y g = g (_Y g)       -- = g (g (g (g (g ... ))))

將素數共遞迴地定義為不是素數倍數的自然數。或者使用陣列，

import Data.Array
import Data.List (tails, inits)

ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2)) ps (inits ps),
              (n,True)    <- assocs (
                                accumArray (\_ _ -> False) True (r+1,q-1)
                     [(m,()) | p <- px, 
                               let s = div (r+p) p * p,  m <- [s,s+p..q-1]] )]

它不僅僅用於快速排序！

Haskell 也用於構建“現實世界”程式，包括 圖形 或 Web 使用者介面。要體驗 Haskell 在現實世界中的應用，請檢視 Haskell wiki 上的 Haskell 中的 Web 框架 和 Haskell 在行業中的應用 文章，或者 darcs，這是一個用 Haskell 編寫的先進的版本控制系統。