如何在haskell中执行有状态列表操作

Question

我需要一个迭代列表并生成一个新列表的操作,其中新列表元素依赖于之前看到的所有元素.为此,我想将累加器/状态从迭代传递到迭代.

想想一个元组列表的例子,元组的组件可以是"未定义的".未定义的值应假定列表中较早的相同组件的最新值(如果有).所以在任何阶段我都会有一个已定义组件的状态,我需要将其传递给下一次迭代.

因此,对于类型列表[l]和累加器/类型状态,a将有类型的函数

f :: a -> l -> (a,l)

即它吐出一个新的列表元素和一个新的累加器.

是否有一个允许简单地将f应用于列表的功能？我看着折叠,扫描和展开,但他们似乎都没有做到这一点.

编辑:虽然状态monad看起来很有希望,但我只能看到我将如何获得最终状态,但我没有看到如何获得新的列表元素.

Answer 1

您可以使用一些标准功能来执行您的要求.

这听起来非常像你想要的mapAccum,所以你只需要导入Data.List并决定你在哪个方向积累.(我怀疑你想要mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]).)

mapAccumL

import Data.List

data Instruction = NoChange | Reset | MoveBy Int

tell :: Int -> Instruction -> (Int,String) -- toy accumulating function
tell n NoChange = (n,"")
tell n Reset = (0,"Reset to zero")
tell n (MoveBy i) = (n+i,"Add "++show i++" to get "++ show (n+i))

这会给

ghci> mapAccumL tell 10 [MoveBy 5, MoveBy 3, NoChange, Reset, MoveBy 7]
(7,["Add 5 to get 15","Add 3 to get 18","","Reset to zero","Add 7 to get 7"])

scanL

但也许你不需要使用全部功能,mapAccum因为有时累加器就是你想要的新列表,所以scanl :: (a -> b -> a) -> a -> [b] -> [a]会做的伎俩

act :: Int -> Instruction -> Int
act n NoChange = n
act n Reset = 0
act n (MoveBy i) = n+i

像这样:

ghci> scanl act 10 [MoveBy 5, MoveBy 3, NoChange, Reset, MoveBy 7]
[10,15,18,18,0,7]

mapAccum的定义

总之,这里是如何mapAccumL和mapAccumR中描述Data.List模块:

mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
mapAccumL _ state []        =  (state, [])
mapAccumL f state (x:xs)    =  (finalstate,y:ys)
                           where (nextstate, y ) = f state x
                                 (finalstate,ys) = mapAccumL f nextstate xs

该mapAccumL函数的行为类似于map和foldl; 它将一个函数应用于列表的每个元素,从左到右传递累加参数,并将该累加器的最终值与新列表一起返回.

mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
mapAccumR _ state []        =  (state, [])
mapAccumR f state (x:xs)    =  (finalstate, y:ys)
                           where (finalstate,y ) = f nextstate x
                                 (nextstate, ys) = mapAccumR f state xs

该mapAccumR函数的行为类似于map和foldr; 它将一个函数应用于列表的每个元素,从右向左传递累加参数,并将该累加器的最终值与新列表一起返回.

Answer 2

你想mapM与联State单子您的蓄电池a将是State.首先,要了解您需要的原因State,只需获取您的类型签名并翻转参数和结果的顺序:

import Data.Tuple

f :: a -> l -> (a, l)

uncurry f :: (a, l) -> (a, l)

swap . uncurry f . swap :: (l, a) -> (l, a)

curry (swap . uncurry f . swap) :: l -> a -> (l, a)

或者你可以定义f已经拥有正确顺序的参数和结果,无论你喜欢哪个.我将调用此交换函数f':

f' :: l -> a -> (l, a)

现在让我们在类型签名的右半部分周围添加一组额外的括号f':

f' :: l -> (a -> (l, a))

括在括号中的那部分是一个State计算,其中状态是a,结果是l.所以我将继续State使用以下state函数将其转换为类型Control.Monad.Trans.State:

state :: (a -> (l, a)) -> State a l

所以转换后f'看起来像这样:

f'' :: l -> State a l
f'' = state . f'

但是,你最终想要的功能是什么类型:

final :: [l] -> a -> ([l], a)

-- which is really just:
state . final :: [l] -> State a [l]

所以这意味着我需要一些函数来获取l -> State a l并将其转换为[l] -> State a [l].这恰恰是什么mapM,除了mapM适用于任何Monad,不仅仅是State:

mapM :: (Monad m) => (a -> m b) -> ([a] -> m [b])

请注意如何,如果我们更换m带State a,并设置a和b到l,那么它有完全正确的类型:

mapM :: (l -> State a l) -> ([l] -> State a [l])

f''' :: [l] -> State a [l]
f''' = mapM f''

现在我们可以解包State使用runState以获取相应类型的列表线程函数:

final :: [l] -> a -> ([l], a)
final = runState . f'''

因此,如果我们将所有这些步骤合并为一个,

final = runState . mapM (state . f')

... f'你的函数在哪里交换参数和结果的顺序.如果您选择不修改原始功能,那么解决方案稍微冗长一点:

final = runState . mapM (state . uncurry (swap . curry f . swap))