3

我想获取一个列表(或一个字符串)并将其拆分为 N 个元素的子列表。我如何在 Haskell 中做到这一点?

例子:

mysteryFunction 2 "abcdefgh"
["ab", "cd", "ef", "gh"]
4

7 回答 7

13
cabal update
cabal install split

然后使用chunksOffromData.List.Split

于 2013-08-25T08:55:55.153 回答
12

这是一个选项:

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)
于 2013-08-25T08:48:09.390 回答
5

你可以使用:

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"]
于 2013-08-25T08:52:20.187 回答
1
import Data.List 
import Data.Function

mysteryFunction n = map (map snd) . groupBy ((==) `on` fst) . zip ([0..] >>= replicate n)

... 只是在开玩笑...

于 2013-08-25T13:42:43.543 回答
1
mysteryFunction x "" = []
mysteryFunction x s = take x s : mysteryFunction x (drop x s)

可能不是您想到的优雅解决方案。

于 2013-08-25T16:47:56.857 回答
1

已经有

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)
于 2013-08-25T17:07:17.173 回答
1

一个花哨的答案。

在上面的答案中,您必须使用 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,它会一步生成列表的其余部分(在这种情况下,只需用 [] 结束列表)。

于 2013-08-27T09:45:20.733 回答