Geek Answers Handbook

How to perform operations with saving a list in haskell

I need an operation that iterates through a list and creates a new list in which new list items depend on all previously found items. For this, I would like to pass the battery / state from iteration to iteration.

Consider, for example, a list of tuples, where the components of a tuple can be "undefined". The value undefined must be the latest value of the same component earlier in the list, if any. Therefore, at any stage, I will have the state of certain components, which I need to pass to the next iteration.

So, with a type list [l]and a battery / type state, athere will be a type function

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

he spits out a new list item and a new drive.

Is there a function that allows you to simply apply f to the list? I looked at the crease, turned and turned, but none of them seemed to do it.

Edit: Although the state monad looks promising, I can only see how to get the final state, but I don’t see how I will get the new list items.

+4
source share
3 answers

There are some standard features that you can use to complete your tasks.

It sounds very similar to what you want mapAccum, so you just need to import Data.Listand decide in which sequence you are accumulating. (I suspect you want to 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))

which would give

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; , .

+7

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))
+5

, , . , f :

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

f':

f' :: (a, [l]) -> l -> (a,l)
f' acc@(y, xs) x = (z, x':xs)
    where
        (z, x') = f acc

.

foldr f' (e, []) xs

f , f' f .

+1

More articles:


All Articles