Является ли (map f) == concatMap (map f. (: []))? - PullRequest
Новая
       20

Является ли (map f) == concatMap (map f. (: []))?

4 голосов
/ 01 августа 2011

Я определил методы left / right для потоковых функций (SF) класса ArrowChoice следующим образом: newtype SF a b = SF { runSF :: [a] -> [b] }

instance ArrowChoice SF where
  left (SF f) =
   SF $ map (either (\x -> Left . head $ f [x]) Right)
  right (SF f) =
   SF $ map (either Left (\x -> Right . head $ f [x]))

Несколько тестов в ghci заставляют его выглядеть так:все в порядке: 

λ> let lst = [Left 'c', Right 2, Left 'a', Right 3, Left 't']
λ> let foo = SF $ map toUpper
λ> let bar = SF $ map (+1)
λ> runSF (left foo) lst
[Left 'C',Right 2,Left 'A',Right 3,Left 'T']
λ> runSF (right bar) lst
[Left 'c',Right 3,Left 'a',Right 4,Left 't']

Но использование его с mapA говорит иначе: 

λ> let delay x = SF $ init . (x:)
λ> runSF (mapA (delay 0)) [[1,2,3],[4,5,6],[7,8,9]]
[[0,0,0],[0,0,0],[0,0,0]]

Правильный ответ должен быть: 

[[0,0,0],[1,2,3],[4,5,6]]

где mapA естьопределяется как: 

mapA :: ArrowChoice arr => arr a b -> arr [a] [b]
mapA f = arr listcase >>>
         (arr (const []) ||| (f *** mapA f >>> arr (uncurry (:))))

1 Ответ

7 голосов
/ 01 августа 2011

Я не думаю, что ваш экземпляр ArrowChoice правильный.

Обратите внимание, что функция delay принимает поток и заменяет первый элемент;критически, это не относится ко всем элементам одинаково.Теперь рассмотрим ваше определение Left: 

left (SF f) = SF $ map (either (\x -> Left . head $ f [x]) Right)

Обратите внимание, что f является кишкой всей функции потока и, следовательно, может вести себя по-разному в зависимости от положения потока.Затем функция left создает новую потоковую функцию, которая отображает однородную функцию в своем потоке, где каждый элемент либо пропускается (для Right s), либо поднимается в одноэлементный список, в который входит входзапускается функция потока.

Вместо delay рассмотрите вместо этого следующую функцию: 

skip = SF $ drop 1

Это полностью удаляет первый элемент потока, и поскольку left выполняет его вводнезависимо каждый раз в списке синглтонов, это отфильтровывает все Left с полностью!Возможно, это не то, что вам нужно.

Скорее, вам нужно сделать что-то вроде разделения потока на его компоненты Left и Right, применить функцию входного потока ко всему потоку * Left s, затем объедините левые и права в ту же последовательность, в которой они были изначально.

У меня сложилось впечатление, что вы делаете это как какое-то упражнение, поэтому я не испорчувесело, просто выписав решение в полном объеме.Но я скажу, что мой код действительно показывает [[0,0,0],[1,2,3],[4,5,6]] на вашем примере.

Если вы хотите увидеть мой тестовый код, он ниже.(тсс, он прячется)

...