Можете ли вы определить минимальное или максимальное значение списка, используя только монаду списка? - PullRequest
Новая
       53

Можете ли вы определить минимальное или максимальное значение списка, используя только монаду списка?

0 голосов
/ 10 ноября 2018

Пытается понять связь между Монадой и Складной. Мне известно, что частью значений классов типов Monad, Applicative и Functor является их способность поднимать функции над структурой, но что, если я хочу сгенерировать итоговое значение (например, min или max) для значений, содержащихся в Monad?

Это было бы невозможно без правильного аккумулятора (как в складном)? А чтобы иметь аккумулятор, нужно вводить или разрушать конструкцию? 

min :: Ord a => a -> a -> a

foldMin :: (Foldable t, Ord a) => t a -> Maybe a
foldMin t = foldr go Nothing t
  where
    go x Nothing = Just x
    go x (Just y) = Just (min x y)

Здесь значением Nothing является аккумулятор. Таким образом, было бы невозможно выполнить операцию, которая выдает итоговое значение, подобное этому, в пределах блока do?

Ответы [ 3 ]

0 голосов
/ 10 ноября 2018

Придуманный и неэффективный код, приведенный ниже, наиболее близок к тому, чтобы «использовать только монаду списка». Это, вероятно, не то, что ищет ОП, но вот оно.

Я также использую head (который вы можете заменить на listToMaybe, если мы хотим тотальность) и null. Я также использую empty (который можно заменить на []).

Код работает, недетерминированно выбирая элемент m, а затем проверяя, что более крупные элементы не существуют. Это имеет квадратичную сложность. 

import Control.Applicative

maximum :: Ord a => [a] -> a
maximum xs = head maxima
   where
   isMax m = null $ do
      x <- xs
      if x > m
         then return x
         else empty
   maxima = do
      m <- xs   -- non deterministically pick a maximum
      if isMax m
         then return m
         else empty
0 голосов
/ 19 ноября 2018

Я также не уверен, каков реальный вопрос, но необходимость в аккумуляторе может быть скрыта с помощью экземпляра Monoid. Затем - для вашего минимального примера - вы можете использовать foldMap из Data.Foldable, чтобы отобразить и объединить все значения вашего Foldable. E.g.:

data Min a = Min { getMin :: Maybe a } deriving Show

instance Ord a => Monoid (Min a) where
  mempty                                = Min Nothing
  mappend a (Min Nothing)               = a
  mappend (Min Nothing) b               = b
  mappend (Min (Just a)) (Min (Just b)) = Min (Just (min a b))

foldMin :: (Foldable t, Ord a) => t a -> Maybe a
foldMin = getMin . foldMap (Min . Just)
0 голосов
/ 10 ноября 2018

Я не совсем уверен, что понимаю вопрос, поэтому простите, если это не полезный ответ, но, насколько я понимаю, суть вопроса такова:

Так что было бы невозможно выполнить операцию, которая выдает итоговое значение, подобное этому, в пределах блока do?

Правильно, это было бы невозможно. Запись do в Haskell - это синтаксический сахар свыше Monad, поэтому в основном синтаксический сахар превышает >>= и return.

return, как вы знаете, не позволяет вам «получить доступ» к содержимому Monad, поэтому единственный доступ к содержимому у вас есть через >>=, и в случае монады списка например, это дает вам только одно значение за раз.

Обратите внимание, что Foldable даже не требует, чтобы контейнер данных был Functor (намного меньше Monad). Известно, что Set не является экземпляром Functor, но является экземпляром Foldable.

Например, вы можете найти минимальное значение в наборе: 

Prelude Data.Foldable Set> foldr (\x -> Just . maybe x (min x)) Nothing $ Set.fromList [42, 1337, 90125, 2112]
Just 42
...