Пользовательских карты Функции: mapLift

Question

После обсуждения моего текущего вопроса на Writing a custom map function, я думал, что я нашел решение моей проблемы:

mapLift :: Monad m => (a -> b) -> [m a] -> [m b] 
mapLift f = map (liftM f) 

Однако, когда я использую его, я получаю ошибку компиляции. Мой фактический код:

actuals  = zipWith mapLift (mapLift eval wffs) assignments 

где

eval :: Wff -> Assignment -> Maybe Bool 
wffs :: [Either String Wff] 
assignments :: [Assignment] 

Этот код дает следующее сообщение об ошибке:

Couldn't match expected type `a0 -> Wff' 
      with actual type `Either String Wff' 
Expected type: [a0 -> Wff] 
    Actual type: [Either String Wff] 
In the second argument of `mapLift', namely `wffs' 
In the second argument of `zipWith', namely `(mapLift eval wffs)' 

Что я делаю неправильно? Я хочу нанести на карту eval более wffs с сохранением любых Left s, которые дают сообщения об ошибках с предыдущего шага в процессе.

Edit:

Первоначально моя идея состояла в том, что actuals :: [Either String (Maybe Bool)]. Тем не менее, я рассматриваю возможность вместо eval вместо eval :: Wff -> Assignment -> Either String Bool, так что actuals :: [Either String Bool].

Update:

я сделал опечатку в моем оригинальный вопрос. assignments должно быть:

assignments :: [[Assignment]] 

Answer 1

Я не совсем уверен, что вы хотите тип actuals быть, но давайте предположим, что это [Either String (Maybe Bool)]. В таком случае, давайте начнем с

actuals = zipWith (\ew a -> undefined) wffs assignments 

где ew является Either String Wff и a является Assignment. Каким должно быть тело нашей функции? Как-то нам нужно поднять eval в Either. Если уступка была в Either, мы могли бы написать liftM2 eval a ew - но это не так. Таким образом, мы можем либо использовать return a здесь, или применить eval его Assignment аргумент сначала flip, а затем поднимите его (или многие другие возможности):

actuals = zipWith (\ew a -> liftM (flip eval a) ew) wffs assignments 

Необязательно, давайте гольф дальше:

actuals = zipWith (\ew -> flip liftM ew . flip eval) wffs assignments 

на мой взгляд, ни один не ясно, как

\ew a -> eval <$> ew <*> return a 

где <$> это другое название для liftM от Control.Applicative. Вы можете узнать больше о <$> и <*> в, например, «Learn вам Haskell», но в основном f <$> ma <*> mb <*> ... <*> mn (эквивалентно liftMn f ma mb ... mn для малых достаточно n) является монадическая (на самом деле, applicative) версия f a ... n.

На этом этапе вы можете извлечь все сбои или что-то еще.Интересно, является ли присутствие Maybe и Either знаком, который вы могли бы немного упростить. Например, если ваш eval может не оценить Wff, вы можете использовать Either вместо Maybe для записи ошибки. Тогда, ошибки будут пойманы на стадии, в которой они происходят, и успехи будут распространяться в обычном пути Either монады:

-- eval :: Wff -> Assignment -> Either String Bool 
actuals :: [Either String Bool] 
actuals = zipWith (\ew a -> ew >>= flip eval a) wffs assignments 

Смотрите также errors пакет, который обеспечивает - среди его многочисленных приветственных особенностей - некоторые полезные комбинаторы, чтобы идти между Either и Maybe.

Я не решил проблему так, как вы предлагали, которая должна была отображаться над первым списком перед тем, как закрепить. Но вы можете сделать это, конечно, тоже:

actuals = zipWith (\ef a -> liftM ($ a) ef) (mapLift eval wffs) assignments 

Здесь liftM ($ a) является умеренно умной альтернативой ef <*> return a.

Это кажется немного шумнее - zipWith - это уже своего рода карта, и вы также можете воспользоваться ею.

EDIT в ответ на редактирование параметров порядка: Если вы хотите actuals :: [[Assignment]], то необходимые изменения просты:

actuals :: [Either String (Maybe Bool)] 
actuals = 
    concat $ zipWith (\ew -> map (liftA2 eval ew . return)) wffs assignments 

Идея здесь я снова начал с чем-то формы concat $ zipWith f wffs assignments для неизвестного f (concat потому, что тип [[]] должен быть сплющен каким-то образом ... если вы забыли его, типы не совсем совпали), а затем запросил компилятор для типа f (путем записи where f ::(); f = undefined и изучения полученного сообщения об ошибке), а затем написал соответствующая функция, затем эта-сниженная (в гольф). GHC 7.8 будет иметь отверстия типа, позволяющие вам получить тип неопределенного, все еще подлежащего письменному выражению, что позволяет использовать гораздо более элегантный способ разработки с использованием типов (TDD), чем это возможно сегодня (за исключением, например, Agda).

Адаптирования это использовать списковые и иметь тип [Either String Bool], согласно моей должности, остаются в качестве полезного упражнения :)

Answer 2

mapLift «s первого аргументом является функцией от a -> b. Вы передаете первый аргумент eval :: Wff -> Assignment -> Maybe Bool. Из-за ассоциативности (->) это означает, что a объединяет Wff и b с Assignment -> Maybe Bool. Это означает, что следующий аргумент mapLift, wffs, как ожидается, будет иметь тип [m Wff], который позволяет m объединиться с Either String. Все в порядке.

Проблема заключается в том, что результат mapLift eval wffs будет в конечном итоге с типом [m b], который, учитывая то, что m и b унифицированы является [Either String (Assignment -> Maybe Bool)]. Это уже идет на юг, но давайте продолжим следовать за ним.

zipWith имеет тип (a -> b -> c) -> [a] -> [b] -> [c], и мы передаем первый аргумент в качестве mapLift :: (s -> t) -> [m s] -> [m t].Это означает, что zipWith заканчивается объединяющее a с типом функции (s -> t), b с [m s] и [c] с [m t] таким образом, что

zipWith mapLift :: [s -> t] -> [[m s]] -> [[m t]] 

Теперь давайте перейдем в результате (mapLift eval wffs) и смотреть фейерверк.

zipWith mapLift :: [s -> t] -> [[m s]] -> [[m t]] 
       (mapLift eval wffs) :: [Either String (Assignment -> Maybe Bool)] 

Для продолжения проверки типов необходимо унифицировать [s -> t] с [Either String (Assignment -> Maybe Bool)]. Наружная [] отправляется немедленно, но нам еще нужно найти способ показать s -> t ~ Either String (Assignment -> Maybe Bool), что просто невозможно из-за обертывания Either String.

---

Проблема заключается в том, что ваши типы не совпадают, потому что ваша семантика отсутствует способ объединения двух видов отказа --- в Either String и Maybe. К счастью, это можно сделать, распакуя Either в функции, которые принимают Assignment. Вот один из способов

fixEither :: Either String (Assignment -> Maybe Bool) -> (Assignment -> Maybe Bool) 
fixEither (Left _) _ = Nothing 
fixEither (Right f) a = f a 

---

Теперь, наконец, если бы мы должны были попытаться запустить

zipWith mapLift (map fixEither $ mapLift eval wffs) assignments 

там все еще будет проблема, как

zipWith mapLift (map fixEither $ mapLift eval wffs) 
    :: [[m Assignments]] -> [[m (Maybe Bool)]] 

пока assignments :: [Assignments] не будет соответствовать , Нам нужно обернуть assignments, по крайней мере, в другом слое [] и некоторых m. Кроме того, неясно, что вы хотите.

---

Это означает, что вы, вероятно, еще недостаточно определили свой алгоритм.

Я бы всегда рекомендовал сделать рекурсивный алгоритм или использовать только «простой» map, чтобы проверить, что вы полностью понимаете, как чередуются различные слои списков и функций и моноды. Ярлыки, предоставленные fmap и liftM, очень эффективны, но требуется некоторое время, чтобы получить право.

Answer 3

fmap или <$> достаточно для этого случая (при условии, выход вы хотите типа [Either String (Maybe Bool)]:

result :: [Either String (Maybe Bool)] 
result = zipWith (<$>) [flip eval $ a | a <- assignments] wffs