Как вернуть функцию, полученную в результате альтернативного объединения двух списков функций в Haskell программировании?

Question

В моем назначении курса Haskell я хочу решить задачу, которая заключается в том, чтобы понять, как обрабатывать списки функций. Входные данные состоят из двух таких списков, скажем, первый из них задан как [A0..AN], а второй - как [B0..BN]. Мне нужно вернуть одну функцию, которая объединяет функции, применяющие их так, чтобы функции чередовались как аргументы вложенной функции внутри выходной функции. На самом деле, это означает, что выходной результат равен единице:

G x = A0 (B0 (A1 (B1 (A2 (B2 (... AN (BN)))))))

My основное решение не работает, есть код, с которого я пытался начать:

funcCarnage :: [a -> a] -> [a -> a] -> (a -> a)
funcCarnage (x:xs) (y:ys) = extraFuncCarnage xs ys x 2 where
extraFuncCarnage bs fs gs n
    | length bs == 0 && length fs == 0 = gs  
    | odd n = extraFuncCarnage (tail bs) fs (gs $ head bs) (n + 1) 
    | otherwise = extraFuncCarnage bs (tail fs) (gs $ head fs) (n + 1) 

Компиляция завершается с ошибочными сообщениями:

* Occurs check: cannot construct the infinite type: a ~ a -> a
  Expected type: a -> a
    Actual type: (a -> a) -> a -> a
* In the expression: extraFuncCarnage xs ys x 2
  In an equation for `funcCarnage':
      funcCarnage (x : xs) (y : ys)
        = extraFuncCarnage xs ys x 2
        where
            extraFuncCarnage bs fs gs n
              | length bs == 0 && length fs == 0 = gs
              | odd n = extraFuncCarnage (tail bs) fs (gs $ head bs) (n + 1)
              | otherwise = extraFuncCarnage bs (tail fs) (gs $ head fs) (n + 1)

* Occurs check: cannot construct the infinite type: t1 ~ t -> t1
  Expected type: [t] -> [t] -> t1 -> a1 -> t -> t1
    Actual type: [t] -> [t] -> (t -> t1) -> a1 -> t -> t1
* In an equation for `funcCarnage':
      funcCarnage (x : xs) (y : ys)
        = extraFuncCarnage xs ys x 2
        where
            extraFuncCarnage bs fs gs n
              | length bs == 0 && length fs == 0 = gs
              | odd n = extraFuncCarnage (tail bs) fs (gs $ head bs) (n + 1)
              | otherwise = extraFuncCarnage bs (tail fs) (gs $ head fs) (n + 1)

Это некоторая неясная жалоба, поэтому я ' Я запутался, как приступить к решению. Как мне исправить оба типа ошибок?

Answer 1

Вы можете сначала объединить два списка, а затем сделать правильное сгиб.

import Control.Applicative(ZipList(..))

funcCarnage fs gs = foldr (.) id list
  where
    list = concat $ getZipList $ (\x y -> [x, y]) <$> ZipList fs <*> ZipList gs 

Answer 2

В других ответах обсуждается, как использовать библиотечные функции в качестве строительных блоков для создания вашей функции. Я думаю, что было бы также интересно посмотреть, как написать рекурсию самостоятельно; в этом случае это особенно просто. Я последую прекрасному предложению Люки в комментариях: сначала написать функцию для чередования двух списков, а затем составить все функции в результате.

interleave :: [a] -> [a] -> [a]
interleave (x:xs) ys = x : interleave ys xs
interleave [] ys = ys

compose :: [a -> a] -> a -> a
compose [] = id
compose (f:fs) = f . compose fs

Затем ваша функция может запустить эти две последовательности:

carnage :: [a -> a] -> [a -> a] -> a -> a
carnage fs gs = compose (interleave fs gs)

Позже, когда вы станете более продвинутым, вы сможете заметить некоторые общие циклические структуры в приведенном выше коде. В частности, compose является вполне стандартной «формой» итерации: сделайте что-нибудь, чтобы объединить определенный элемент с результатом выполнения рекурсивного вызова. Эта форма настолько распространена, что у нас есть стандартная библиотечная функция для ее инкапсуляции. foldr принимает функцию объединения (которая объединяет один элемент с результатом рекурсивного вызова) и результат базового случая в качестве аргументов, затем выполняет итерацию, поэтому:

compose :: [a -> a] -> a -> a
compose = foldr (.) id

l oop в interleave - менее распространенная форма, хотя иногда она возникает в различных обстоятельствах. Одним из способов является думать об этом как почтовый индекс; или вы можете заметить, что транспонирование матрицы - это, по сути, произвольный почтовый индекс, и повторно использовать эту операцию. Итак:

interleave :: [a] -> [a] -> [a]
interleave xs ys = concat (transpose [xs, ys])

На этом этапе реализации функций для compose и interleave настолько коротки, что вы можете рассмотреть возможность их вставки, если не считаете, что имена являются важной частью объяснительная сила кода. Итак:

carnage :: [a -> a] -> [a -> a] -> a -> a
-- was: carnage fs gs = compose (interleave fs gs)
carnage fs gs = foldr (.) id (concat (transpose [fs, gs]))

Идиоматически, Haskell программисты обычно предпочитают цепочки композиции функций вложенным скобкам:

carnage fs gs = foldr (.) id . concat . transpose $ [fs, gs]

На мой опытный взгляд, это выглядит компактно и читабельно; Я бы остановился там.

Answer 3

Я использовал это

funcCarnage :: [a -> a] -> [a -> a] -> (a -> a)
funcCarnage xs ys = foldl1 (.) $ zipWith (.) xs ys

Не уверен, правильно ли я использовал фолд.

Применение

funcCarnage [(+) 10, (*) 2] [(+) 3, (*) 5] $ 9

дает 103.

См. ZVON для получения некоторой информации о (.).