在同一时间做递归和计数数字哈斯克尔

如果我有一个已知列表A :: [Int]，并希望得到一个新的列表B = newList A与newList定义如下：在同一时间做递归和计数数字哈斯克尔

newList :: [Int] -> [Int] 
newList [] = [] 
newList (a:as) | a==0  = f(a) : newList (as) 
       | a==1  = g(a) : newList (as) 
       | otherwise = h(a) : newList (as)

其中f, g, h :: Int -> Int是不重要的功能。

除B以外，我也想知道在A中分别有多少个0, 1。

但自从生成B递归时，它已经检查了A中的每个元素是否为a== (0 or 1)，因此它是冗余的，可以再次单独检查它。

是否有可能得到B但同时得到有多少个0, 1在那里A只检查一次？

来源

2015-10-20 CYC

首先，您可以用值'f 0'和'g（a）'与值'g 1'交换'f（a）' - 然后是可以的，例如您可以使用'foldr '这样做 - 也许你想在我们破坏它之前先看看它？ – Carsten

提示：这个想法是将列表折叠成一个元组''（na，nb，xs）'，其中'na'是*看到的数量*'a's，'n''与'b's相同和'xs'就是你在这里用'map h'完成的映射列表（使用'foldr'首先查找'map'的方式 - 附加提示：使用'（：）'和'[]';） – Carsten

' mapAccumR'也可以提供帮助，因为它将折叠与地图结合在一起。 – chi

这不是你正在寻找一个答案，但你的函数身后一个漂亮的抽象结构，所以我会离开这里：

import Data.Monoid 
import Data.Functor 
import Data.Traversable 
import Control.Arrow 
import Control.Monad.Trans.Writer 

wr :: Int -> Writer (Sum Int, Sum Int) Int 
wr 0 = tell (Sum 1, Sum 0) $> f 0 
wr 1 = tell (Sum 0, Sum 1) $> g 1 
wr n = return $ h n 

collect :: [Int] -> ([Int], (Int, Int)) 
collect = second (getSum *** getSum) . runWriter . traverse wr

求和是幺，双求和是幺，Writer monad处理monoids，traverse映射具有有效功能的列表并执行所有效果。

此：

f = (+ 1) 
g = (+ 2) 
h = (+ 3) 

main = print $ collect [0, 1, 2, 3, 0, 0, 0, 4, 1]

打印([1,3,5,6,1,1,1,7,3],(4,2)) - 四个零和两个人。

来源

2015-10-20 20:42:01 user3237465

在同一时间做递归和计数数字哈斯克尔

回答

相关问题