В чем разница между этими функциями mondai c? - PullRequest
Новая
       28

В чем разница между этими функциями mondai c?

2 голосов
/ 18 июня 2020

Итак, у меня есть эти две функции: 

filterM _ [] = []
filterM p (x:xs) = do
                  n <- p x
                  ys <- filterM p xs
                  return (if n then x:ys else x:xs)

и 

filterM _ [] = return []
filterM p (x:xs) = do
                  n <- p x
                  ys <- filterM p xs
                  return (if n then x:ys else x:xs)

В результате получаются эти результаты для следующего ввода: filterM (\x -> [True,False]) [0..3]

[]

или 

[[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3]]

Почему return так сильно влияет на выполнение?

1 Ответ

4 голосов
/ 18 июня 2020

Давайте рассмотрим простой случай, когда мы вызываем: 

filterM (const [True, False]) [0]

Мы ожидаем, что это вернет [[0], [0]]. Если мы посмотрим на первую реализацию, мы увидим, что это приведет к: 

filterM (const [True, False]) (0:[]) = do
    n <- [True, False]
    ys <- <b>filterM (const [True, False]) []</b>
    return (if n then 0:ys else 0:[])

Если мы возьмем первую реализацию, filterM (const [True, False]) [] приведет к []. Это означает, что это будет выглядеть так: 

-- first implementation
filterM (const [True, False]) (0:[]) = do
    n <- [True, False]
    ys <- <b>[]</b>
    return (if n then 0:ys else 0:[])

Поскольку для instance Monad [], >>= реализовано как : 

instance Monad [] where
    return x = [x]
    xs >>= f = [y | x <- xs, y <- f x]

это означает, что если xs пусто, то результат также будет пустым.

Во второй реализации return [] приведет к [[]] , так что одноэлементный список , где единственный элемент является пустым списком. В этом случае это выглядит так: 

-- second implementation
filterM (const [True, False]) (0:[]) = do
    n <- [True, False]
    ys <- <b>[[]]</b>
    return (if n then 0:ys else 0:[])

Это означает, что мы выполняем перечисление по списку, а ys примет значение [], поэтому в результате получится список [[0], [0]] .

Обычно фильтр не добавляет x в обоих случаях, кроме того, вы, вероятно, захотите получить x:ys и ys; не x:ys и x:xs. Таким образом, правильная реализация: 

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
filterM _ [] = return []
filterM p (x:xs) = do
    n <- p x
    ys <- filterM p xs
    return (if n then <b>x:ys</b> else <b>ys</b>)
...