Хаскелл: мемлекеттегі итерация, менің қалаған мінез-құлықты қалай мәжбүрлеу керек?

Бұл менің алғашқы хабарымды SO-де жарияладым және мен Хаскеллге қатысты жаңа болып табыламын, сондықтан кез келген қателіктерді кешіріңіз немесе егер менің кодым идоматтық емес болса!

Келесі екі интуитивті сипаттамасын қарастырайық: a, f (a), f (f (a)) ...

A. a list containing: a, the application of f to a, the application of f to that, the application of f to that...

B. a list containing, in the ith position, i nested applications of f to a.

Мәселе мынада, мен Haskell-те A iterate функциясын қолдануға тырысты. Менің нақты қолданылымым - бұл модельдеу, бірақ келесі мысал келтіреді, бұл мәселені ерекше көрсетеді.

import Control.Monad.State

example :: State Int [[String]]

step :: [String] -> State Int [String]
step l = do
         currentState <- get
         let result = if (currentState == 1)
                          then "foo":l
                          else "bar":l
         put (currentState + 1)
         return result

example = do
          sequence $ take 3 . iterate (>>= step) $ return []

Осы анықтамалармен,

evalState example 1

нәтижелері:

[[],["foo"],["bar","bar"]]

Әрине, iterate B емес, A ! step функциясы кіріс тізіміне тек қана қосады функциясы болғандықтан step [«foo»] [« бар «,» бар «] , қарамастан, мемлекет қандай!

step - бұл функция, мұнда не болып жатқанын түсінуім керек, сонымен қатар, формальді түрде нәтиже дәл осы « сондықтан f (a) f (f (a)) бөлігі ретінде бағалау үшін шықса, ол екінші өзгерді, себебі мемлекет өзгерді. Сондай-ақ, мен өзімнің жинақтаушы тізімді мемлекетке қою арқылы нақты өмірлік тәжірибемнен аулақ бола алатынымды түсінемін.

Дегенмен, оны жариялаудың екі себебі бар.

Ең алдымен, iterate дегеніміз, B B деп ойлайтын бастаушыға ықтимал қателерді азайтатын тәсілмен жиі түсіндіріледі >. Бұған Learn A Haskell (мен басқаша керемет пайдалы деп таптым) кіреді, сонымен қатар SO-да ( мұнда және мұнда , мысалы). Шындығында, LYAHFGG-дегі iterate -дің ауызша түсіндірмесі, жоғарыдағы A анықтамасы. Сондықтан, осыған орай, осыған байланысты қате жіберген және түсіндірме іздейтін басқа да Haskell жаңалықтары үшін ресурс ретінде бұл қызметтің болуы пайдалы болуы мүмкін (сондықтан да дәлірек айтқанда, техникалық, жақсы тұжырымдалған, A және B арасындағы айырмашылық).

Екіншіден, мен A жасайтын функция бар-жоғын білмеймін! Басқаша айтқанда, мен жоғарыда келтірілген мысалда тізімді жасай аламын (белгілердің сәл теріс пайдалануы): [a, b = f (a), f (b), ...]? Басқаша айтқанда, берілген

example2 = do
           firstResult <- step []
           secondResult <- step firstResult
           return $ [[], firstResult, secondResult]

олар үшін

evalState example2 1

қажетті нәтиже береді

[[],["foo"],["bar","foo"]]

iterate арқылы example2 қалай қайта жазуға болады?

Хаскелл тізімінде жаңадан байланысты сұраққа қатысты. iterate -нің есте сақтау нұсқасы орналастырылды. Алайда, бұл сұрақ жауап алған жоқ сияқты.

Мен жалғандық менің өтінішімде шынымен де проблема болғанына сенімдімін. iterate қатаң нұсқасы менің қалағанымды істей ме? Менің жеке, аңғалдық, «қатаң итерация» төмендегідей ешқандай айырмашылықты тудырмайды.

iterate' f x = x : rest
               where previous = f x
                     rest = previous `seq` iterate f previous

Мұның бәрі туралы қандай да бір түсінікке ие болар едік!

4

2 жауаптар

There is no difference between A. and B., they are the same thing by referential transparency.
The core of the problem seems to be that you're interpreting them in the context of execution of stateful computations. In that context, the analogue of A that you're expecting is
A': Produce a result list by 1. putting the result of the initial computation into the list, 2. determine the next computation from the previous result, execute it and append its result to the list, 3. goto 2.
The analogue of B is
B': Produce a list of computations (by iterating (>>= step)) and from that a result list by executing the computations one after the other.
For stateless computations, or when you pass the same initial state to all computations produced in B', the only difference is in efficiency, but if you're using sequence, each computation starts with a different state, so you get different results from A'. Breaking down your example, we have

actionList = take 3 $ iterate (>>= step) (return [])
           = [return [], return [] >>= step, return [] >>= step >>= step]

State Int [String] ішіндегі әрекеттер тізімі (немесе монадические мәндер). Енді тізбегін қолданған кезде,

example = sequence actionList

орындалатын кезде, осы әрекеттердің біріншіін бастапқы күйде іске қосатын әрекетті, екіншісі күймен жаңартылған күйде, ал екіншісі күйде жаңартылған күйде болады. Сіз күткен мінез-құлықты алу үшін олардың барлығы бірдей бастапқы күйде жұмыс істеуге тура келеді.

Basically, a value of type State s v is a function of type s -> (v, s). iterate creates a list of functions, and sequence applys these functions, supplying different s arguments to them (each gets the s produced by the previous).

Қажетті әрекетті алу үшін жаңа комбинаторды енгізу керек. Өте жақсы, бірақ өте аз Монадта қолдануға болады

iterateM :: Monad m => (a -> m a) -> m a -> m [a]
iterateM step start = do
    first <- start
    rest <- iterateM step (step first)
    return (first:rest)

Қандай өндіріс

Prelude Control.Monad Control.Monad.State> evalState (fmap (take 4) (iterateM step (return []))) 1
[[],["foo"],["bar","foo"],["bar","bar","foo"]]

But it works only in monads with sufficiently lazy (>>=), Control.Monad.State.Lazy is one of the few, Control.Monad.State.Strict is not. And even with C.M.S.Lazy, You cannot use the state after an iterateM, you have to put a new state before you can continue the computation. To get something usable with other monads, we could add a count parameter,

iterCountM :: (Monad m) => Int -> (a -> m a) -> m a -> m [a]
iterCountM 0 _ _ = return []
iterCountM k step start = do
    first <- start
    rest <- iterCountM (k-1) step (step fisrt)
    return (first:rest)

сондықтан біз икемділікті жоғалтып аламыз, бірақ көп монадисте ыңғайлылыққа ие боламыз.

16
қосылды
Жауап үшін көп рахмет! «Мысалыңызды бұзғаннан кейін ...» деп айтқаныңыздың бәрі мағынасын жасайды және «Мен мұнда не болып жатқанын түсінемін» деп айтқым келеді. Осылайша растау үшін рақмет. Бірақ түсіндіруге әлі де сенбедім. A деген екінші элемент бірінші элементтің толық бағаланған нәтижесіне қадам [«foo»] қадамының қолданылуы дегенді білдіреді [«bar», «bar»] , ол ешқашан болмайды, күйге қарамастан . Осы түсіндірмені ескере отырып, мысал B орындалады, бірақ A емес, сондықтан олар тең болмайды.
қосылды автор Bilal Barakat, көзі
Барлық реттелген әрекеттерді сол бастапқы күйде іске қосу мұнда мағынасы бар. Алайда, менің нақты қолданымда, мемлекет сонымен қатар кездейсоқ генераторды қамтиды және әрбір қадам ішінде бірнеше стохастический оқиғалар орын алады. Мәселен, егер мен бірдей кездейсоқ генератордың нәтиже тізіміндегі әрбір позициядағы «бірінші» қадамға берілуін қамтамасыз етсем, олар әр түрлі нәтижелерге әкелуі мүмкін, дұрыс? Бірақ екінші жазба енді бірінші эволюция ретінде түсіндірілмеуі мүмкін ...
қосылды автор Bilal Barakat, көзі
Иә, бұл дәл менің ойлап тапқан үлгіім. Сонымен, бұл example2 сілтемесі бойынша (түпнұсқалық сұраққа редакциялау), келесі жауап болады: «сіз iterate көмегімен қайта жазылмайсыз!» ? Сонда, мұны істеу үшін бірдей ықшам/талғампаздық/идиоматикалық тәсіл қандай еді? Мен айтқанымдай, мен мұны мемлекеттің ішіндегі нәтиже жинақтамастан жасауға мүдделі болар едім.
қосылды автор Bilal Barakat, көзі
Дэниел, егер сіз өзіңіздің екінші пікіріңізді (контекстпен) бөлек жауапта жазсаңыз, онда мен дауыс бере аламын ... (Менің ойымша, сіздің алғашқы жауапыңыз - example бұл жасайды, мен жай ғана басқаша нәрсе жасау үшін басшылық іздеймін!)
қосылды автор Bilal Barakat, көзі
бұл керемет көмек, жомарт көмек үшін алғыс айтамын!
қосылды автор Bilal Barakat, көзі
Менің жалғыз сөзбе-сөз, бұл жауапты iterate (ол B ) және iterateM (әрине A орындалатын) шынымен әртүрлі ... Егер A және B сөз тіркесі бар болса, сияқты екі иераторлар сияқты), біз екі сұрақты да түзете аламыз және сәйкесінше жауап бере аламыз. Менің позициямыздағы біреу үшін пайдалы ресурстық ресурсқа әкеледі деп ойлаймын. Мен оны қабылдағаннан кейін жауапты өңдеу мүмкін емес деп ойлаймын ба?
қосылды автор Bilal Barakat, көзі
@Carl Кіргеніңіз үшін рахмет, бірақ Дэниел мен үшін бәрін тазалады. Мен жоғалып кеткен басқатырғыштың бөлігі сіз ойлағандай емес, бірақ ешқашан ойланбайды. Сұрағым үшін кешірім сұраймын, бірақ сол кездегі жаңалық ретінде: осы жолдардағы қосымша түсініктемелерді болдырмау үшін бастапқы сұрақты өңдеу керек пе?
қосылды автор Bilal Barakat, көзі
Жаңа типтегі қаптамаларды ескерместен, итерат сізге функциялардың тізімін (модульдік жаңа түр және currying, (>> = step) :: (([String], Int) -> ([String], Int) ) -> (([String], Int) -> ([String], Int)) ). Әрбір функция осы функцияның алдыңғы функцияға қолданылуының нәтижесі болып табылады (толық бағаланған немесе референс мөлдірлігінен маңызды емес). Алдыңғы функцияның қолданылуының нәтижесін келесі анықтамаға қосқыңыз келеді, бұл қайталанатын емес, басқа үлгі.
қосылды автор Daniel Fischer, көзі
@Bilal, мен өзімнің алғашқы жауапыма басшылық қостым, бұл көмектеседі деп үміттенемін.
қосылды автор Daniel Fischer, көзі
Менің ойымша, қабылданған жауаптарды түзету мүмкін, бірақ оны түсіндіру туралы ойлануға рұқсат етіңіз. Мәселе итерация түрінде A және B бірдей нәрсе, бірақ сіз А-ның басқа түрін алғыңыз келеді.
қосылды автор Daniel Fischer, көзі
@BilalBarakat A және B - бұл бірдей нәрсе. Сіз бастапқы қадамды бірінші қадам деп атағаныңыз туралы болжамды әрдайым жасайсыз: 1. Кезектілікті пайдалануыңыздың арқасында бұл дұрыс емес. Мемлекет контексінде кезектілік «бірінші әрекетті ағымдағы жағдаймен орындап, нәтижені келесі әрекетке өткізіп, оны орындауға және т.б. орындауға және соңғы әрекеттің нәтижесі ретінде ағымдағы жағдайды жаңартуға» білдіреді. Сіз «әр іс-әрекетті ағымдағы күйде орындаңыз» деп болжап отырған сияқтысыз.
қосылды автор Carl, көзі

Бұл сіз берген мәселеге жауап бермеуі мүмкін, бірақ сіз істеп жатқан нәрсе, unfoldr секілді өте жаман нәрсе естіледі.

step (seed, l) = Just (l', (seed', l'))
  where seed' = succ seed
        l' = (if seed == 1 then "foo" else "bar"):l

ghci> take 3 $ unfoldr step (1, [])
[["foo"], ["bar", "foo"], ["bar", "bar", "foo"]]

Монады қажет емес. Мен қараңғыда соққыға ұқсаймын, сіз шынымен не істеп жатқаныңызды көрсетпегендіктен, бірақ step құқығым бар ма, жоқ па, бұл unfoldr код> қарапайым күйді бұру үшін де пайдалануға болады.

unfoldr :: (seed -> Maybe (val, seed)) -> seed -> [val]
3
қосылды
Рахмет @Dan, nice tipp, және шынымен мен білмеген unfoldr (қарамастан, мен картасын пайдалана отырып, картасынAccumL). Мен міндетті түрде бұл менің құралдарыма қосатын боламын, бірақ менің қазіргі мақсатым үшін әр «қадам» өте қызықтырады және әлі де кеңейе түсуі мүмкін, сондықтан монадтың жалпылығы пайдалы болуы мүмкін.
қосылды автор Bilal Barakat, көзі
+1 төмен бағаны көтермелеу үшін.
қосылды автор Daniel Fischer, көзі