列表基础 #

-- 列表示例
numbers :: [Int]
numbers = [1, 2, 3, 4, 5]

chars :: [Char]
chars = ['h', 'e', 'l', 'l', 'o']

-- String是[Char]的类型别名
text :: String
text = "hello"  -- 等价于 ['h', 'e', 'l', 'l', 'o']

-- 列表类型语法
-- [元素类型]

[Int]        -- 整数列表
[String]     -- 字符串列表
[[Int]]      -- 整数列表的列表
[(Int, String)]  -- 元组列表

-- 同类型元素
valid = [1, 2, 3]        -- OK
-- invalid = [1, "two", 3]  -- 错误！类型不一致

-- 不可变
xs = [1, 2, 3]
-- xs[0] = 10  -- 错误！列表不可修改

-- 惰性
infinite = [1..]  -- 无限列表，按需求值

-- 枚举范围
[1..5]      -- [1, 2, 3, 4, 5]
['a'..'e']  -- "abcde"
[1..]       -- 无限列表 [1, 2, 3, ...]

-- 指定步长
[1, 3..10]  -- [1, 3, 5, 7, 9]
[10, 9..1]  -- [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[0, 0.5..2] -- [0.0, 0.5, 1.0, 1.5, 2.0]

-- 列表构造器 : (cons)
-- : :: a -> [a] -> [a]

-- 使用构造器
empty = []
one = 1 : []
two = 1 : 2 : []
three = 1 : 2 : 3 : []

-- 等价于
three' = [1, 2, 3]

-- 模式匹配
head' (x:_) = x
tail' (_:xs) = xs

-- ++ 运算符
-- (++) :: [a] -> [a] -> [a]

[1, 2] ++ [3, 4]      -- [1, 2, 3, 4]
"hello" ++ " world"   -- "hello world"

-- 多次拼接
[1] ++ [2] ++ [3]     -- [1, 2, 3]

-- 注意：++会遍历左边的列表
-- 对于大量拼接，使用:
1 : 2 : 3 : []        -- 比 [1, 2] ++ [3] 更高效

-- head：第一个元素
head [1, 2, 3]  -- 1

-- last：最后一个元素
last [1, 2, 3]  -- 3

-- tail：除第一个外的所有元素
tail [1, 2, 3]  -- [2, 3]

-- init：除最后一个外的所有元素
init [1, 2, 3]  -- [1, 2]

-- !!：索引访问（从0开始）
[1, 2, 3, 4, 5] !! 2  -- 3

-- 注意：以上函数对空列表会报错
-- head []  -- 错误！

-- 安全版本
safeHead :: [a] -> Maybe a
safeHead []    = Nothing
safeHead (x:_) = Just x

safeTail :: [a] -> Maybe [a]
safeTail []     = Nothing
safeTail (_:xs) = Just xs

safeIndex :: [a] -> Int -> Maybe a
safeIndex xs n
    | n < 0 || n >= length xs = Nothing
    | otherwise               = Just (xs !! n)

-- length：长度
length [1, 2, 3, 4, 5]  -- 5

-- null：是否为空
null []      -- True
null [1, 2]  -- False

-- elem：是否包含元素
3 `elem` [1, 2, 3, 4, 5]  -- True
6 `elem` [1, 2, 3, 4, 5]  -- False

-- notElem：是否不包含
3 `notElem` [1, 2, 3]  -- False

-- take：取前n个元素
take 3 [1..10]  -- [1, 2, 3]
take 5 [1, 2]   -- [1, 2]  -- 不会越界

-- drop：丢弃前n个元素
drop 3 [1..10]  -- [4, 5, 6, 7, 8, 9, 10]
drop 5 [1, 2]   -- []  -- 不会越界

-- splitAt：在指定位置分割
splitAt 3 [1..6]  -- ([1, 2, 3], [4, 5, 6])

-- takeWhile：取满足条件的元素
takeWhile (< 5) [1..10]  -- [1, 2, 3, 4]

-- dropWhile：丢弃满足条件的元素
dropWhile (< 5) [1..10]  -- [5, 6, 7, 8, 9, 10]

-- span：分割为满足和不满足两部分
span (< 5) [1..10]  -- ([1, 2, 3, 4], [5, 6, 7, 8, 9, 10])

-- break：span的否定
break (> 5) [1..10]  -- ([1, 2, 3, 4, 5], [6, 7, 8, 9, 10])

-- filter：过滤
filter even [1..10]  -- [2, 4, 6, 8, 10]

-- map：映射
map (*2) [1, 2, 3]  -- [2, 4, 6]

-- 组合使用
map (*2) (filter even [1..10])  -- [4, 8, 12, 16, 20]

-- zip：配对两个列表
zip [1, 2, 3] ['a', 'b', 'c']  -- [(1, 'a'), (2, 'b'), (3, 'c')]

-- 长度不同时以短的为准
zip [1, 2, 3] ['a', 'b']  -- [(1, 'a'), (2, 'b')]

-- zipWith：配对并应用函数
zipWith (+) [1, 2, 3] [4, 5, 6]  -- [5, 7, 9]

-- zip3：三个列表配对
zip3 [1, 2, 3] ['a', 'b', 'c'] [True, False, True]
-- [(1, 'a', True), (2, 'b', False), (3, 'c', True)]

-- unzip：解配对
unzip [(1, 'a'), (2, 'b'), (3, 'c')]  -- ([1, 2, 3], "abc")

-- unzip3：解三个配对
unzip3 [(1, 'a', True), (2, 'b', False)]
-- ([1, 2], "ab", [True, False])

-- concat：拼接列表的列表
concat [[1, 2], [3, 4], [5, 6]]  -- [1, 2, 3, 4, 5, 6]

-- concatMap：映射后拼接
concatMap show [1, 2, 3]  -- "123"

-- intercalate：用分隔符拼接
import Data.List (intercalate)
intercalate ", " ["a", "b", "c"]  -- "a, b, c"

-- elem：是否包含
elem 3 [1, 2, 3, 4, 5]  -- True

-- notElem：是否不包含
notElem 6 [1, 2, 3, 4, 5]  -- True

-- lookup：在关联列表中查找
lookup 2 [(1, "one"), (2, "two"), (3, "three")]  -- Just "two"
lookup 4 [(1, "one"), (2, "two")]  -- Nothing

import Data.List

-- elemIndex：元素位置
elemIndex 3 [1, 2, 3, 4, 5]  -- Just 2
elemIndex 6 [1, 2, 3]        -- Nothing

-- elemIndices：所有位置
elemIndices 'a' "banana"  -- [1, 3, 5]

-- findIndex：满足条件的位置
findIndex (> 3) [1, 2, 3, 4, 5]  -- Just 3

-- findIndices：满足条件的所有位置
findIndices even [1, 2, 3, 4, 5, 6]  -- [1, 3, 5]

import Data.List

-- find：查找满足条件的元素
find (> 3) [1, 2, 3, 4, 5]  -- Just 4
find (> 5) [1, 2, 3]        -- Nothing

-- filter：查找所有满足条件的元素
filter (> 3) [1, 2, 3, 4, 5]  -- [4, 5]

import Data.List

-- sort：排序
sort [3, 1, 4, 1, 5, 9, 2, 6]  -- [1, 1, 2, 3, 4, 5, 6, 9]

-- sort字符串
sort "hello"  -- "ehllo"

-- sort列表的列表
sort [[3, 1], [2, 2], [1, 3]]  -- [[1, 3], [2, 2], [3, 1]]

import Data.List

-- sortBy：自定义比较
sortBy (flip compare) [1, 2, 3]  -- [3, 2, 1]  -- 降序

-- 按长度排序
sortBy (compare `on` length) ["abc", "de", "fghij"]
-- ["de", "abc", "fghij"]

-- 按元组元素排序
sortBy (compare `on` fst) [(3, 'a'), (1, 'b'), (2, 'c')]
-- [(1, 'b'), (2, 'c'), (3, 'a')]

import Data.List

-- group：分组相邻相同元素
group [1, 1, 2, 2, 2, 3, 1, 1]
-- [[1, 1], [2, 2, 2], [3], [1, 1]]

-- groupBy：自定义分组
groupBy (\x y -> (x > 0) == (y > 0)) [-2, -1, 0, 1, 2]
-- [[-2, -1], [0], [1, 2]]

-- groupSort：排序后分组
groupSort xs = group (sort xs)

-- reverse：反转列表
reverse [1, 2, 3, 4, 5]  -- [5, 4, 3, 2, 1]

reverse "hello"  -- "olleh"

-- reverse实现
reverse' :: [a] -> [a]
reverse' []     = []
reverse' (x:xs) = reverse' xs ++ [x]

-- 高效实现（尾递归）
reverse'' :: [a] -> [a]
reverse'' xs = go xs []
  where
    go [] acc     = acc
    go (x:xs) acc = go xs (x:acc)

-- all：所有元素满足条件
all even [2, 4, 6, 8]  -- True
all even [2, 3, 4]     -- False

-- any：任一元素满足条件
any even [1, 3, 5, 6]  -- True
any even [1, 3, 5]     -- False

-- and：布尔列表全部为True
and [True, True, True]   -- True
and [True, False, True]  -- False

-- or：布尔列表任一为True
or [False, True, False]  -- True
or [False, False, False] -- False

-- null：是否为空
null []      -- True
null [1, 2]  -- False

-- elem：是否包含
elem 3 [1, 2, 3, 4, 5]  -- True

-- 统计元素出现次数
count :: Eq a => a -> [a] -> Int
count x = length . filter (== x)

-- 统计所有元素出现次数
frequency :: Eq a => [a] -> [(a, Int)]
frequency xs = map (\x -> (x, count x xs)) (nub xs)
  where
    nub [] = []
    nub (x:xs) = x : nub (filter (/= x) xs)

-- 按条件分区
partition :: (a -> Bool) -> [a] -> ([a], [a])
partition p xs = (filter p xs, filter (not . p) xs)

-- 示例
partition even [1..10]  -- ([2, 4, 6, 8, 10], [1, 3, 5, 7, 9])

-- 获取唯一元素
unique :: Eq a => [a] -> [a]
unique = nub
  where
    nub [] = []
    nub (x:xs) = x : nub (filter (/= x) xs)

-- 列表差集
difference :: Eq a => [a] -> [a] -> [a]
difference xs ys = filter (`notElem` ys) xs

-- 列表交集
intersection :: Eq a => [a] -> [a] -> [a]
intersection xs ys = filter (`elem` ys) xs

-- 列表并集
union :: Eq a => [a] -> [a] -> [a]
union xs ys = xs ++ filter (`notElem` xs) ys