Đệ quy trong một đơn nguyên

Question

Tôi không hiểu được sự đệ quy trong một đơn nguyên. Từ wiki haskell.org đây là một ví dụ:

main = f 3 

f 0 = return [] 
f n = do v <- getLine 
     vs <- f (n-1) 
     return $! v : vs 

Chương trình này nhận ba dòng từ đầu vào chuẩn đệ quy. Những gì tôi không thể hiểu được là những gì sẽ xảy ra khi bạn nhận được để f 0 và làm thế nào đệ quy thư giãn. Giá trị cuối cùng của khối do được xây dựng như thế nào? Tại sao dòng trả lại cuối cùng được gọi lặp đi lặp lại trong đệ quy? Tôi biết trả lại không phải là chức năng trở lại như trong ngôn ngữ mệnh lệnh, nhưng tôi không thể nhìn thấy cách dòng này được lặp đi lặp lại.

Tôi biết rằng đây là câu hỏi về người mới bắt đầu thô, nhưng tôi bị bối rối.

Answer 1

Trong trường hợp cụ thể này, bạn chỉ có thể mở ra hoàn toàn. Có lẽ điều này sẽ giúp:

f 3 
= { reduce f (and the subtraction) } 
    do v <- getLine 
    vs <- f 2 
    return $! v : vs 
= { reduce f (and the subtraction) } 
    do v <- getLine 
    vs <- do v' <- getLine 
       vs' <- f 1 
       return $! v' : vs' 
    return $! v : vs 
= { reduce f (and the subtraction) } 
    do v <- getLine 
    vs <- do v' <- getLine 
       vs' <- do v'' <- getLine 
         vs'' <- f 0 
         return $! v'' : vs'' 
       return $! v' : vs' 
    return $! v : vs 
= { reduce f } 
    do v <- getLine 
    vs <- do v' <- getLine 
       vs' <- do v'' <- getLine 
         vs'' <- return [] 
         return $! v'' : vs'' 
       return $! v' : vs' 
    return $! v : vs 
= 
    ... 

Tại thời điểm này, không còn đệ quy nào. Tất cả những gì chúng tôi đã làm là áp dụng các định nghĩa chức năng. Từ đây, chúng ta có thể đơn giản hóa hơn nữa nếu chúng ta giả định rằng luật đơn nguyên giữ:

... 
= { vs'' <- return [] means that vs'' is [] } 
    do v <- getLine 
    vs <- do v' <- getLine 
       vs' <- do v'' <- getLine 
         return $! v'' : [] 
       return $! v' : vs' 
    return $! v : vs 
= { inline the innermost do block } 
    do v <- getLine 
    vs <- do v' <- getLine 
       v'' <- getLine 
       vs' <- return $! v'' : [] 
       return $! v' : vs' 
    return $! v : vs 
= { inline return $! v'' : [] } 
    do v <- getLine 
    vs <- do v' <- getLine 
       v'' <- getLine 
       return $! v' : v'' : [] 
    return $! v : vs 
= { inline the innermost do block } 
    do v <- getLine 
    v' <- getLine 
    v'' <- getLine 
    vs <- return $! v' : v'' : [] 
    return $! v : vs 
= { inline return $! v' : v'' : [] } 
    do v <- getLine 
    v' <- getLine 
    v'' <- getLine 
    return $! v : v' : v'' : [] 

Answer 2

Bạn có thể "giả biên dịch"/"thư giãn" khối monadic để xem làm thế nào nó hoạt động:

f 3 = do v <- getLine 
     vs <- f 2 -- (will return a list with 2 lines from stdin 
     return $! v : vs 
f 2 = do v <- getLine 
     vs <- f 1 -- (will return singleton list with a line from stdin) 
     return $! v : vs 
f 1 = do v <- getLine 
     vs <- f 0 -- (will return an empty list) 
     return $! v : vs 
f 0 = return [] 

Vì vậy, nó sẽ getLine 3 lần và sau đó xây dựng một danh sách các dòng, dòng đầu tiên sẽ là giá trị đầu tiên trong danh sách.

Mỗi khi bạn nhìn thấy một return trong một biểu thức đơn thuần, bạn đang đặt một giá trị bên trong nó. Mỗi khi bạn nhìn thấy một <- (ràng buộc) trong một biểu thức đơn thuần, bạn đang lấy giá trị từ nó. Trong trường hợp của IO đơn nguyên, bạn luôn đặt và lấy ra một đơn lẻ. Ngược lại, danh sách đơn nguyên có thể "lấy ra" (ràng buộc) các giá trị liên tiếp.