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 编写的先进的版本控制系统。