Kleisli 작곡 및 무한리스트 위의 접기

Question

하스켈을 사용하여 연결 채널에서 읽는 무한 루프를 정의하려고 할 때, 나는 부분적으로 적용된 함수의 무한한 목록을 모나드의 Kleisli 구성으로 접는 것에 대해 생각해 보았습니다. 그 아이디어는 그럴듯하고 단순 해 보였지만 입력을 기다리는 대신 무한한 목록을 평가하는 이상한 시나리오를 발견했습니다. 나는 위의 코드를 실행하면

loop :: Int -> IO Int 
loop s = (foldr (<=<) return (repeat process)) s 

process :: Int -> IO Int 
process i = do 
    putStrLn $ show i 
    x <- getLine 
    return $ i + 1 

main = loop 0 

, GHCi는 스택 오버 플로우 후 중지 :

나는 내 문제를 보여 다음 예제를 만들었습니다. "getLine"을 기다리지 않습니다. < = <을> =>으로 바꿀 때 예상대로 작동합니다. 목록은 각 "getLine"후에 요소별로 평가 된 요소 만 가져옵니다.

왜 이런 일이 발생합니까? 내 foldr 초기 값은 반환 값이며, 모나드 법칙에 따라 부작용을 추가해서는 안되며, 왼쪽 및 오른쪽 ID는 < = < 및> =>을 모두 사용하여 동일한 동작을 보장해야합니다.

Answer 1

끝에서 무한한 목록을 방문 할 수는 없습니다. 끝이 없습니다.

당신의 코드는 x 전 (대략 말하기)

action0 <=< (action1 <=< (action2 ....)) 

권리 연관성을 가지고

, 하지만x <=< y 실행 y을 구축합니다.

>=>을 사용하면 action0으로 계산이 시작됩니다.

이와 비교 :

cons x xs = x : xs 
snoc x xs = xs ++ [x] 

foldr cons [] [1..] = [1..] 
foldr snoc [] [1..] = _|_ 

이것은 foldr snoc [] = reverse 이후, 놀라운 일이 아니다, 우리는 무한 목록을 취소 할 수 없습니다. 여기

문제는 너무 foldr 손에있는 요소를 고려하기 전에 꼬리 목록에 "재귀 호출을"평가, snoc이 x 전에 꼬리 xs를 평가한다는 것입니다.

모나드의 경우 상황은 더 복잡하지만 일반적인 원칙은 그 정신이 비슷합니다. 실패 - s을 적용하는 가장 안쪽의 기능을 평가하는

foldr (<=<) return (repeat process) s 
-- becomes 
(process <=< (process <=< (process … <=< return))) s 

: foldr (<=<) return (repeat action)를 사용하는 대신

loop x = do 
    x' <- loop x 
    action x' 

비슷 foldr (>=>) return (repeat action)는 foldr을 확장

loop x = do 
    x' <- action x 
    loop x' 

Answer 2

시도와 유사하다 당연하지. 반대로

foldr (>=>) return (repeat process) s 
-- becomes 
(process >=> (process >=> (process … >=> return))) s 

어떤 경우 s을인가하면 체인의 첫 번째 기능으로 전달되며, 다음의 함수에 그 결과를 전달하는 경우에만 체인의 나머지를 평가한다 - 느리게.나는 생각하지 않는다

는 배를 이용하여 순서

(return >=> (process >=> (process >=> (process …)))) s 

를 구성 할 수있는 방법이 있습니다,하지만 당신은 fixpoint의 콤비 사용할 수 있습니다

fix (process >=>) s -- `return >=>` is a pointless `id` in front 
-- or 
fix (<=< process) s 

공지 사항을 그와 매우 유사 fix (>=> process) 및 fix (process <=<)에는 적용 할 첫 번째 함수를 찾기 위해 영원히 노력하면서 동일한 무한 재귀 문제가 있습니다. 이 같은

Answer 3

foldr 작품 :

xs = 
    a : (b : (c : ... (d : nil)...)) 
foldr kons knil xs = 
    a `kons` (b `kons` (c `kons` ... (d `kons` knil)...)) 

따라서, 귀하의 경우 : 당신이 응용 프로그램 (f <=< g) x을 수행 할 때

repeat process = 
    process : (process : (process : ...)) 
foldr (<=<) return (repeat process) = 
    process <=< (process <=< (process <=< ...)) 

지금, 먼저 g x을 적용해야합니다. 귀하의 경우 (process <=< (process <=< (process <=< ...))) x을 적용하려면 먼저 (process <=< (process <=< (process <=< ...))) x을 적용해야하므로 (process <=< (process <=< (process <=< ...))) x, ...을 먼저 적용해야합니다.

솔루션은 (당신이 알고있는) (f >=> g) x을 적용하려면 (<=<)

foldr (>=>) return (repeat process) = 
    process >=> (process >=> (process >=> ...)) 

(>=>)에 플립하는 것입니다, 먼저 f x을 적용해야합니다. 귀하의 경우에는 (process >=> (process >=> (process >=> ...))) x을 적용하려면 먼저 작동해야하는 process x을 적용해야하며 (process >=> (process >=> (process >=> ...))) x'을 적용해야합니다. 그러면 작동하는 process x'을 적용한 다음 (process >=> (process >=> (process >=> ...))) x''을 적용해야하므로 process x''을 적용해야합니다. ....

런타임은 결과가 동일한 방식이어야 함을 신경 쓰지 않습니다. 그 속성을 확인하는 것은 가능한 모든 경우에 대해 해결할 수없는 중지 문제를 해결하는 것을 의미합니다. 하스켈은 불가능한 일을 시도하는 것보다 천천히 혼란스럽게되는 것이 더 좋을 것입니다.