Haskell: Làm thế nào để đơn giản hóa hoặc loại bỏ liftM2?

Question

Xét đoạn mã sau tôi đã viết:

import Control.Monad 

increasing :: Integer -> [Integer] 
increasing n 
    | n == 1 = [1..9] 
    | otherwise = do let ps = increasing (n - 1) 
        let last = liftM2 mod ps [10] 
        let next = liftM2 (*) ps [10] 
        alternateEndings next last 
    where alternateEndings xs ys = concat $ zipWith alts xs ys 
      alts x y = liftM2 (+) [x] [y..9] 

đâu increasing n 'nên trả về một danh sách các số n chữ số mà số tăng (hoặc giữ nguyên) từ trái sang phải.

Có cách nào để đơn giản hóa điều này không? Việc sử dụng 'let' và 'liftM2' ở khắp mọi nơi trông xấu với tôi. Tôi nghĩ rằng tôi đang thiếu một cái gì đó quan trọng về danh sách monad, nhưng tôi dường như không thể loại bỏ chúng.

Answer 1

Tôi nghĩ rằng những gì bạn đang cố gắng làm là thế này:

increasing :: Integer -> [Integer] 
increasing 1 = [1..9] 
increasing n = do p <- increasing (n - 1) 
        let last = p `mod` 10 
         next = p * 10 
        alt <- [last .. 9] 
        return $ next + alt 

Hoặc, sử dụng một "danh sách hiểu biết", mà chỉ là đặc biệt cú pháp đơn nguyên cho các danh sách:

increasing2 :: Integer -> [Integer] 
increasing2 1 = [1..9] 
increasing2 n = [next + alt | p <- increasing (n - 1), 
           let last = p `mod` 10 
            next = p * 10, 
           alt <- [last .. 9] 
       ] 

Ý tưởng trong danh sách đơn lẻ là bạn sử dụng "liên kết" (<-) để lặp qua danh sách giá trị và let để tính toán một giá trị duy nhất dựa trên những gì bạn có cho đến thời điểm hiện tại. Khi bạn sử dụng liên kết lần thứ hai, các lần lặp được lồng nhau từ điểm đó.

Answer 2

Vâng, theo như chức năng liftM, cách ưa thích của tôi để sử dụng chúng là các bộ phối hợp được xác định trong Control.Applicative. Sử dụng chúng, bạn có thể viết last = mod <$> ps <*> [10]. Chức năng ap từ Control.Monad cũng giống như vậy, nhưng tôi thích phiên bản infix.

Điều gì (<$>) và (<*>) như sau: liftM2 chuyển chức năng a -> b -> c thành một hàm m a -> m b -> m c. Đồng bằng liftM chỉ là (a -> b) -> (m a -> m b), giống như fmap và cũng là (<$>).

Điều gì sẽ xảy ra nếu bạn thực hiện điều đó với chức năng đa đối số? Nó biến thành một cái gì đó như a -> b -> c -> d thành m a -> m (b -> c -> d). Đây là nơi ap hoặc (<*>) đến: những gì họ làm là biến một cái gì đó như m (a -> b) thành m a -> m b. Vì vậy, bạn có thể giữ chuỗi nó theo cách đó cho nhiều đối số tùy thích.

---

Điều đó nói rằng, Travis Brown chính xác là, trong trường hợp này, có vẻ như bạn không thực sự cần bất kỳ điều nào ở trên. Trong thực tế, bạn có thể đơn giản hóa chức năng của mình rất nhiều: Ví dụ: cả last và next có thể được viết dưới dạng các hàm đối số đơn được ánh xạ trên cùng một danh sách, ps và zipWith giống như zip và map. Tất cả các bản đồ này có thể được kết hợp và đẩy xuống chức năng alts. Điều này làm cho alts một hàm đối số đơn lẻ, cũng loại bỏ cả zip. Cuối cùng, concat có thể được kết hợp với map là concatMap hoặc, nếu được ưu tiên, (>>=). Dưới đây là những gì nó kết thúc:

increasing' :: Integer -> [Integer] 
increasing' 1 = [1..9] 
increasing' n = increasing' (n - 1) >>= alts 
    where alts x = map ((x * 10) +) [mod x 10..9] 

Lưu ý rằng tất cả refactoring tôi đã làm để có được phiên bản mà từ bạn đã hoàn toàn cú pháp, chỉ áp dụng biến đổi đó sẽ không có tác động đến kết quả của hàm. Lý luận bình đẳng và minh bạch tham chiếu là tốt đẹp!

Answer 3

Có vẻ rất khác thường khi tôi sử dụng liftM2 (hoặc <$> và <*>) khi một trong các đối số luôn là danh sách đơn. Tại sao không chỉ sử dụng map? Sau đây làm điều tương tự như mã của bạn:

increasing :: Integer -> [Integer] 
increasing n 
    | n == 1 = [1..9] 
    | otherwise = do let ps = increasing (n - 1) 
        let last = map (flip mod 10) ps 
        let next = map (10 *) ps 
        alternateEndings next last 
    where alternateEndings xs ys = concat $ zipWith alts xs ys 
     alts x y = map (x +) [y..9] 

Answer 4

Đây là cách tôi muốn viết mã của bạn:

increasing :: Integer -> [Integer] 
increasing 1 = [1..9] 
increasing n = let allEndings x = map (10*x +) [x `mod` 10 .. 9] 
       in concatMap allEndings $ increasing (n - 1) 

tôi đến mã này như sau. Điều đầu tiên tôi làm là sử dụng mẫu phù hợp thay vì bảo vệ, vì nó rõ ràng hơn ở đây.Điều tiếp theo tôi làm là loại bỏ liftM2 s. Chúng không cần thiết ở đây, bởi vì chúng luôn được gọi với một danh sách kích thước một; trong trường hợp đó, nó giống như gọi map. Vì vậy, liftM2 (*) ps [10] chỉ là map (* 10) ps và tương tự cho các trang web cuộc gọi khác. Nếu bạn muốn có một sự thay thế chung của liftM2, tuy nhiên, bạn có thể sử dụng Control.Applicative 's <$> (mà chỉ fmap là) và <*> để thay thế cho bất kỳ liftMnn: liftMn f a b c ... z trở thành f <$> a <*> b <*> c <*> ... <*> z. Có hay không nó đẹp hơn là một vấn đề của hương vị; Tôi tình cờ thích nó. Nhưng ở đây, chúng ta có thể loại bỏ hoàn toàn.

Địa điểm tiếp theo tôi đơn giản hóa mã gốc là do .... Bạn không bao giờ thực sự tận dụng thực tế là bạn đang ở trong một -block do, và do đó, mã có thể trở thành

let ps = increasing (n - 1) 
    last = map (`mod` 10) ps 
    next = map (* 10)  ps 
in alternateEndings next last 

Từ đây, đến mã của tôi chủ yếu viết tham gia pha trộn tất cả các map bạn s với nhau. Một trong những cuộc gọi còn lại duy nhất không phải là map là zipWith. Nhưng vì bạn có hiệu quả là zipWith alts next last, bạn chỉ làm việc với 10*p và p `mod` 10 cùng một lúc, vì vậy chúng tôi có thể tính toán chúng trong cùng một chức năng. Điều này dẫn đến

let ps = increasing (n - 1) 
in concat $ map alts ps 
where alts p = map (10*p +) [y `mod` 10..9] 

Và điều này về cơ bản là mã của tôi: concat $ map ... nên luôn luôn trở thành concatMap (trong đó, tình cờ, là =<< trong danh sách đơn nguyên), chúng tôi chỉ sử dụng ps một lần vì vậy chúng tôi có thể gấp nó vào, và tôi thích let đến where.

---

1: Về mặt kỹ thuật, điều này chỉ làm việc cho Applicative s, vì vậy nếu bạn tình cờ được sử dụng một đơn nguyên đã không được thực hiện một, <$> là `liftM` và <*> là `ap`. Tất cả các monads có thể được thực hiện functors applicative, mặc dù, và nhiều người trong số họ đã được.

Answer 5

Tôi nghĩ rằng nó sạch hơn để vượt qua chữ số cuối cùng trong một thông số riêng biệt và danh sách sử dụng.

f a 0 = [[]] 
f a n = do x <- [a..9] 
      k <- f x (n-1) 
      return (x:k) 

num = foldl (\x y -> 10*x + y) 0 

increasing = map num . f 1