递归是你的好帮手,但我会稍微改变一下方法。首先,在分割时,我会将我的条件设置为 True 而不是 False。其次,我会使用来自 Data.List
的一个方便函数叫做 break
。
> :t break
break :: (a -> Bool) -> [a] -> ([a], [a])
> break (== ' ') "This is a test"
("This", " is a test")
我会使用它来定义我的函数:
splitWith' :: (a -> Bool) -> [a] -> [[a]]
splitWith' cond [] = []
splitWith' cond xs = first : splitWith' cond (safeTail rest)
where
(first, rest) = break cond xs
safeTail [] = []
safeTail (_:ys) = ys
或者,如果您想尽可能地让它变得混乱
splitWith'' :: (a -> Bool) -> [a] -> [[a]]
splitWith'' _ [] = []
splitWith'' cond xs = uncurry (:) $ fmap (splitWith'' cond . safeTail) $ break cond xs
where
safeTail [] = []
safeTail (_:ys) = ys
这段代码之所以可行,是因为对于2元组,
fmap
会将函数应用于元组的第二个元素。然后它会解开
:
的柯里化,并将其应用于第一个元素和剩余部分。
更新
如果你想在谓词为false时拆分它,你可以使用
span
代替
break
,或者只需定义它为:
splitWithWeird cond xs = splitWith' (not . cond) xs
尽管第二个选项显然会产生稍微小一些的开销(除非编译器可以优化掉它)。
更新2
如果您想处理重复字符,如果适合您的需求,有一个简单快速的解决方法:
> filter (not . null) $ splitWithWeird (/= ' ') "This is a test"
["This","is","a","test"]
使用这样简单的修复方法,我们可能会想要将其构建到算法本身中:
splitWithWeird :: (a -> Bool) -> [a] -> [[a]]
splitWithWeird cond [] = []
splitWithWeird cond xs = filter (not . null) $ first : splitWithWeird cond (safeTail rest)
where
(first, rest) = span cond xs
safeTail [] = []
safeTail (_:ys) = ys
但这是不明智的。由于这是一个递归函数,您在每个级别上都添加了对filter(not.null)
的调用,因此在函数中的每个拆分位置上都要进行扫描整个列表,因此需要执行额外的检查。最好将其定义为单独的函数,以便只调用一次filter(not.null)
:
splitWithWeird' :: (a -> Bool) -> [a] -> [[a]]
splitWithWeird' cond xs = filter (not . null) $ splitWithWeird cond xs
或者,如果您想将其内置到算法中:
splitWithWeird :: (a -> Bool) -> [a] -> [[a]]
splitWithWeird cond xs = filter (not . null) $ splitWithHelper cond xs
where
safeTail [] = []
safeTail (_:ys) = ys
splitWithHelper cond [] = []
splitWithHelper cond xs =
let (first, rest) = span cond xs
in first : splitWithHelper cond (safeTail rest)
这实际上只是在内部定义两个函数所做的相同的事情。请注意,我必须在这里使用额外的 let ... in ...
语句(我不喜欢嵌套 where 语句),因为 (first, rest) = span cond xs
属于 splitWithHelper
,而不属于 splitWithWeird
。如果你将其留在 where 子句中,算法将无法工作。
更新3
为了不仅提供一个不理想的解决方案,我已经编写了一个基于子序列而不仅仅是条件或元素拆分的算法。它确实使用了来自 Control.Arrow
的 first
函数,但仅仅是为了使代码更加紧凑。
import Control.Arrow (first)
isPrefixOf :: Eq a => [a] -> [a] -> Bool
isPrefixOf [] _ = True
isPrefixOf _ [] = False
isPrefixOf (x:xs) (y:ys) = x == y && isPrefixOf xs ys
splitSubseq :: Eq a => [a] -> [a] -> [[a]]
splitSubseq sub [] = []
splitSubseq sub xs = initial : splitSubseq sub rest
where
lsub = length sub
splitter [] = ([], [])
splitter yss@(y:ys)
| isPrefixOf sub yss = ([], drop lsub yss)
| otherwise = first (y :) $ splitter ys
(initial, rest) = splitter xs
我并不是说这是一种高效的解决方案,但它应该相当容易理解。首先,我定义了一个名为
isPrefixOf
的函数,如果第二个列表以第一个列表开头,则返回True。
我想保持递归的相同模式(
first : recursive rest
),因此我编写了
splitter
来替代
span
或
break
,这就是
isPrefixOf
的作用所在。如果子序列是列表的前缀,则返回
([],restAfterSubsequence)
,否则它存储列表的第一个字符,然后从下一个元素开始重复此操作。我在这里使用
first
只是为了能够简洁地递归编写此函数。它只是将
(y:)
应用于
splitter
的返回值的第一个元素。从
splitter
返回的元组的第二个元素只是尚未使用的输入的其余部分。
如果您感兴趣,这是该算法的性能统计数据(使用
--make -O2
编译,i5四核):
main = print $ sum $ take (10 ^ 7) $ map length $ splitSubseq " " $ cycle "Testing "
70000000
6,840,052,808 bytes allocated in the heap
2,032,868 bytes copied during GC
42,900 bytes maximum residency (2 sample(s))
22,636 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 13114 colls, 0 par 0.06s 0.07s 0.0000s 0.0001s
Gen 1 2 colls, 0 par 0.00s 0.00s 0.0002s 0.0004s
TASKS: 3 (1 bound, 2 peak workers (2 total), using -N1)
SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)
INIT time 0.00s ( 0.00s elapsed)
MUT time 3.68s ( 3.74s elapsed)
GC time 0.06s ( 0.07s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 3.74s ( 3.81s elapsed)
然后去嵌入求和和长度:
main = print $ sum $ take (10 ^ 7) $ map length $ repeat "Testing"
70000000
240,052,572 bytes allocated in the heap
12,812 bytes copied during GC
42,900 bytes maximum residency (2 sample(s))
22,636 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 458 colls, 0 par 0.00s 0.00s 0.0000s 0.0000s
Gen 1 2 colls, 0 par 0.00s 0.00s 0.0001s 0.0001s
TASKS: 3 (1 bound, 2 peak workers (2 total), using -N1)
SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.09s ( 0.09s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.11s ( 0.09s elapsed)
因此,我们可以看到这只需要大约0.1秒的时间,留下大约3.64秒的时间来将一个由
“Testing”
重复10百万次构成的字符串分割开,同时仅使用少量内存。唯一的缺点是,当使用
-threaded
编译并在多个核心上运行时,这种算法实际上会显着减慢速度。
splitWith (== ' ') "This is a test"
时,我得到了[" "," "," "]
,但如果我将它从==
改为/=
,我会得到["This","is","a","test"]
。你想在条件为假的地方分割,还是在条件为真的地方分割? - bheklilr