我想获取一个列表(或一个字符串)并将其拆分为 N 个元素的子列表。我如何在 Haskell 中做到这一点?
例子:
mysteryFunction 2 "abcdefgh"
["ab", "cd", "ef", "gh"]
我想获取一个列表(或一个字符串)并将其拆分为 N 个元素的子列表。我如何在 Haskell 中做到这一点?
例子:
mysteryFunction 2 "abcdefgh"
["ab", "cd", "ef", "gh"]
cabal update
cabal install split
然后使用chunksOf
fromData.List.Split
这是一个选项:
partition :: Int -> [a] -> [[a]]
partition _ [] = []
partition n xs = (take n xs) : (partition n (drop n xs))
这是该函数的尾递归版本:
partition :: Int -> [a] -> [[a]]
partition n xs = partition' n xs []
where
partition' _ [] acc = reverse acc
partition' n xs acc = partition' n (drop n xs) ((take n xs) : acc)
你可以使用:
mysteryFunction :: Int -> [a] -> [[a]]
mysteryFunction n list = unfoldr takeList list
where takeList [] = Nothing
takeList l = Just $ splitAt n l
或者:
mysteryFunction :: Int -> [a] -> [[a]]
mysteryFunction n list = unfoldr (\l -> if null l then Nothing else Just $ splitAt n l) list
请注意,这会将所有剩余元素放在最后一个列表中,例如
mysteryFunction 2 "abcdefg" = ["ab", "cd", "ef", "g"]
import Data.List
import Data.Function
mysteryFunction n = map (map snd) . groupBy ((==) `on` fst) . zip ([0..] >>= replicate n)
... 只是在开玩笑...
mysteryFunction x "" = []
mysteryFunction x s = take x s : mysteryFunction x (drop x s)
可能不是您想到的优雅解决方案。
已经有
Prelude Data.List> :t either
either :: (a -> c) -> (b -> c) -> Either a b -> c
和
Prelude Data.List> :t maybe
maybe :: b -> (a -> b) -> Maybe a -> b
所以真的应该有
list :: t -> ([a] -> t) -> [a] -> t
list n _ [] = n
list _ c xs = c xs
也是。用它,
import Data.List (unfoldr)
g n = unfoldr $ list Nothing (Just . splitAt n)
没有它,
g n = takeWhile (not.null) . unfoldr (Just . splitAt n)
一个花哨的答案。
在上面的答案中,您必须使用 splitAt,它也是递归的。让我们看看如何从头开始构建递归解决方案。
Functor L(X)=1+A*X 可以将 X 映射为 1 或将其拆分为一对 A 和 X,并以 List(A) 作为其最小不动点: List(A) 可以映射为 1+ A*List(A) 并返回使用同构;换句话说,我们有一种方法可以分解一个非空列表,而只有一种方法可以表示一个空列表。
Functor F(X)=List(A)+A*X 是类似的,但是列表的尾部不再是一个空列表——“1”——所以 functor 能够提取一个值 A 或者把 X 变成一个列表作为。那么 List(A) 是它的不动点(但不再是最小不动点),函子可以将任何给定的列表表示为一个列表,或者表示为一个元素和一个列表的对。实际上,任何代数都可以“随意”“停止”分解列表。
{-# LANGUAGE DeriveFunctor #-}
import Data.Functor.Foldable
data N a x = Z [a] | S a x deriving (Functor)
(这与添加以下平凡实例相同):
instance Functor (N a) where
fmap f (Z xs) = Z xs
fmap f (S x y) = S x $ f y
考虑hylomorphism的定义:
hylo :: (f b -> b) -> (c -> f c) -> c -> b
hylo psi phi = psi . fmap (hylo psi phi) . phi
给定一个种子值,它使用 phi 生成 fc,fmap 递归地应用 hylo psi phi,然后 psi 从 fmapped 结构 f b 中提取 b。
这个函子的(共)代数对的一个子态是 splitAt:
splitAt :: Int -> [a] -> ([a],[a])
splitAt n xs = hylo psi phi (n, xs) where
phi (n, []) = Z []
phi (0, xs) = Z xs
phi (n, (x:xs)) = S x (n-1, xs)
这个余代数提取一个头,只要有一个头要提取并且提取的元素的计数器不为零。这是因为函子是如何定义的:只要 phi 产生 S xy,hylo 就会将 y 作为下一个种子提供给 phi;一旦产生了 Z xs,仿函数就不再对它应用 hylo psi phi,并且递归停止。
同时 hylo 会将结构重新映射成一对列表:
psi (Z ys) = ([], ys)
psi (S h (t, b)) = (h:t, b)
所以现在我们知道 splitAt 是如何工作的。我们可以使用同态将其扩展到 splitList:
splitList :: Int -> [a] -> [[a]]
splitList n xs = apo (hylo psi phi) (n, xs) where
phi (n, []) = Z []
phi (0, xs) = Z xs
phi (n, (x:xs)) = S x (n-1, xs)
psi (Z []) = Cons [] $ Left []
psi (Z ys) = Cons [] $ Right (n, ys)
psi (S h (Cons t b)) = Cons (h:t) b
这一次重新映射适合使用无同素:只要它是正确的,无同素将继续使用 hylo psi phi 产生列表的下一个元素;如果它是 Left,它会一步生成列表的其余部分(在这种情况下,只需用 [] 结束列表)。