Wie man eine Funktion über eine Liste mit vorherigen Ausgaben als Argumente anwendet?

Question

Ich habe eine Funktion f :: (a -> a) -> a -> ((a -> a), a). (Im speziellen Fall ist aInt, aber das ist ohne Bedeutung.)

Ich habe eine Funktion initial :: a -> a, und eine Liste der Eingänge (inputs :: [a]).

benötigen I f an alle Elemente der inputs anzuwenden, aber für jeden, den ich fst Teil der Ausgabe von der vorherigen Iteration ergreifen müssen, und ihn als das (a -> a) Teil der Eingang für den nächsten. Als Ausgang muss ich eine Liste vom Typ [a] haben, die der snd Teil der Ausgänge jeder Iteration ist.

Wie kann ich rekursiv anwenden f zum fst Teil der Ausgabe und die Elemente der inputs, während eine Liste der Zwischen snd Teilen des Ausgangs Aufbau?

Answer 1

Sie mögen vielleicht mapM. Darunter gebe ich den Typ, den es hat, eine Spezialisierung dieses Typs, die Neuausweitung des spezialisierten Typs und eine weitere Spezialisierung. Der endgültige Typ sollte Ihnen ziemlich vertraut vorkommen. Ich benutze ~:: um informell zu meinen "ungefähr hat den Typ".

mapM :: Monad m => (a -> m b) -> [a] -> m [b] 
mapM :: (a -> State s b) -> [a] -> State s [b] 
mapM ~:: (a -> s -> (s, b)) -> [a] -> s -> (s, [b]) 
mapM ~:: (a -> (a -> a) -> (a -> a, a)) -> [a] -> (a -> a) -> (a -> a, [a]) 

Der letzte Typ beschreibt genau das, was Sie tun wollen: Es kann dauern (eine leicht modifizierte) f, inputs und initial als Argumente und produzieren die Liste der Ausgänge (zusammen mit einigen Zusatzinformationen).

Answer 2

Klingt für mich wie scanl helfen könnte:

scanl g (initial, undefined) xs 
    where g (i,_) a = f i a 

das Anfangselement aus der Ergebnisliste zu entfernen (was immer 1 länger sein wird als die Eingabeliste), gilt ein tail zum Ergebnis bei.