주름으로 모나드 액션을 구성합니다

Question

유형의 함수를 가져 가자 (Monad m) => a -> m a. 예를 들어:

ghci> let f x = Just (x+1)

나는 그것을 여러 번 적용 할 수 있기를 원합니다. 내가 시도한 첫 번째 것은

ghci> let times n f = foldr (>=>) return $ replicate n f

문제는 그것이 크게 작동하지 않는다는 것입니다 n:

ghci> 3 `times` f $ 1
Just 4
ghci> 1000000 `times` f $ 1
Just *** Exception: stack overflow

다른 방식으로는 작동하지 않습니다.

ghci> let timesl n f = foldl' (<=<) return $ replicate n f
ghci> 3 `timesl` f $ 1
Just 4
ghci> 1000000 `timesl` f $ 1
Just *** Exception: stack overflow

실제로, 작동하는 것은 사용 중입니다 ($!) 엄격한 연산자

ghci> let timesStrict n f = foldr1 ((>=>) . ($!)) $ replicate n f
ghci> 3 `timesStrict` f $ 1
Just 4
ghci> 10000000 `timesStrict` f $ 1
Just 10000001

더 좋거나 더 관용적 인 해결책이 있습니까? 아니면 아마도 더 엄격한 것일까 요? 나는 여전히 쉽게 스택 오버 플로우를 얻는다 f 무거운 체중 기능입니다.

upd : 나는 그 글을 발견했다 times 뾰족한 형태로는 무거운 체중 모나디아 행동을 구성하는 문제를 해결하지 못한다. 이것은 FX = Just (x+1)에서 작동하지만 실제 세계에서는 실패합니다.

times f 0 a = return a
times f i a = (f $! a) >>= times f (i - 1)

Answer 1

당신이 만든 경우 f 엄격합니다

f x = let y = x+1 in y `seq` Just y

또는

-- remember to enable -XBangPatterns
f !x = Just (x+1)

나머지를 내버려두면 코드가 매우 큰 상태에서도 일정한 공간에서 실행됩니다. n:

ghci> times 4000000000 f 3
Just 4000000003

Answer 2

아마도 기존 기능의 더 엄격한 변형을 만들었을 것입니다.

{-# LANGUAGE BangPatterns #-}
iterate' f !x = x : iterate' f (f x)
ma >>=! f = do !a <- ma; f a
times' n f a = iterate' (>>=! f) (return a) !! n

아마도 당신의 문제는 그 사실에서 비롯됩니다 seq WHNF에 대한 첫 번째 주장 만 평가합니까? 복잡한 구조로 작업하는 경우 더 깊이 필요할 수 있습니다. seq, 처럼 DeepSeq.

Answer 3

나는 이것을 생각해 냈다 :

 last $ take n $ iterate (>>= f) $ Just 1

그러나 그것은 또한 많은 수의 스택을 지나치게 흐릅니다. n. 나는 지금 그것을 더 많이 조사 할 시간이 없다 :-(