P28 - 按子列表长度排序
Sorting a list of lists according to length of sublists
官方模块：
Problems.P28核心函数：lsort,lfsort
题目描述
实现两个排序函数：
lsort xs：按子列表的长度升序排列lfsort xs：按子列表的出现频率排序——即按子列表的长度在整个大列表中出现的频率排序
函数签名
1lsort :: [[a]] -> [[a]]
2lfsort :: [[a]] -> [[a]]
实现
lsort 方法一：sortBy + comparing
1import Data.List (sortBy)
2import Data.Ord (comparing)
3
4lsort :: [[a]] -> [[a]]
5lsort = sortBy (comparing length)
用 comparing length 生成比较器，按 length 排序。等价于 sortOn length。
lsort 方法二：sortOn
1import Data.List (sortOn)
2
3lsort :: [[a]] -> [[a]]
4lsort = sortOn length
标准库推荐的写法，GHC 的 sortOn 用装饰-排序-去装饰（Schwartzian transform）优化，比 sortBy 少做重复计算。
lsort 方法三：手动插入排序
1lsort :: [[a]] -> [[a]]
2lsort [] = []
3lsort (x:xs) = insertByLen x (lsort xs)
4 where
5 insertByLen y [] = [y]
6 insertByLen y (z:zs)
7 | length y <= length z = y : z : zs
8 | otherwise = z : insertByLen y zs
纯递归，不依赖标准库排序函数。适合教学演示排序原理，但效率远不如 sortOn。
lfsort 方法一：Map 计数
1import Data.List (sortOn)
2import qualified Data.Map.Strict as Map
3
4lfsort :: [[a]] -> [[a]]
5lfsort xs = sortOn frequency xs
6 where
7 counts = Map.fromListWith (+) [(length ys, 1 :: Int) | ys <- xs]
8 frequency ys = Map.findWithDefault 0 (length ys) counts
先统计每种长度出现的次数（一个 Map），然后按这个次数排序。
注意：这里引入
Int类型注解1 :: Int，避免Num默认类型歧义。
lfsort 方法二：group + sortOn 组合
1import Data.List (sortOn, groupBy)
2import Data.Function (on)
3
4lfsort :: [[a]] -> [[a]]
5lfsort = concat . sortOn length . groupBy ((==) `on` length) . sortOn length
先按长度排序，然后把相同长度的子列表分组，再按组的长度（即该长度出现的次数）排序这些组，最后 concat 展平。
这种方法巧妙利用了 groupBy 本身的分组能力，不依赖 Map。
lsort 方法对比
| 方法 | 代码量 | 效率 | 特点 |
|---|---|---|---|
| sortBy + comparing | 1 行 | O(n log n) | 显式比较器 |
| sortOn | 1 行 | O(n log n) | Schwartzian 变换，推荐 |
| 手写插入排序 | 8 行 | O(n²) | 教学用途 |
测试
1>>> lsort ["xxx","xx","xxx","xx","xxxx","xx","x"]
2["x","xx","xx","xx","xxx","xxx","xxxx"]
3>>> lfsort ["xxx","xx","xxx","xx","xxxx","xx"]
4["xxxx","xxx","xxx","xx","xx","xx"]
5>>> lsort []
6[]