Haskell динамически транспонировать несколько списков в один список рекурсивно

Question

Не уверен, что «динамически» - правильное слово для этой проблемы.

Я некоторое время пытался найти решение для объединения нескольких списков в один список, но я начинаю думать что мой подход невозможен. Это хорошо работает для двух списков, но не для трех (и, вероятно, не более трех). Предполагается, что функция работает как transpose, но в результате получается список целых чисел, а не список целых чисел. Но если это приводит к списку списков, это также будет работать. Теоретически, функция должна работать для произвольного количества списков.

Например, [1,2,3] myTranspose [4,5,6] myTranspose [7,8,9] должно привести к [ 1, 4, 7, 2, 5, 8, 3, 6, 9]

Возможно ли это?

Моя попытка на данный момент:

myTranspose :: [Int] -> [Int] -> [Int]
myTranspose [] []         = []
myTranspose [x] []        = [x]
myTranspose [] [y]        = [y] 
myTranspose [x] [y]       = [x,y]
myTranspose (x:xs) [y]    = (x:y:xs)
myTranspose [x] (y:ys)    = (x:y:ys)
myTranspose (x:xs) (y:ys) = [x,y] ++ zip' xs ys

ИЗМЕНИТЬ МОЙ АКТУАЛЬНАЯ ЗАДАЧА:

Я должен был спросить об этом с самого начала, но я подумал, что было бы проще преобразовать задачу в список целых чисел. Извините за это.

У меня есть тип данных Function и функция, которая связывает Function с:

data Function where
    (|||) :: Function -> Function -> Function
    A ::  Char -> Function
    B ::  Int  -> Function

chain :: Function -> Function -> Function
chain f1 f2 = f1 ||| f2

И у меня также есть функция, которая должна работать например, транспонирование, как я описал выше:

(<|||>) :: Funcion -> Function -> Function
 ...something like this..
(<|||>) (p1 ||| p2) (q1 ||| q2)     =  (p1 <|||> q1) ||| (p2 <|||> q2)
(<|||>) (p1 ||| p2)       q          =  p1 <|||> p2 ||| q 
(<|||>)       p         (q1 ||| q2)  =  p  ||| q1 <|||> q2
(<|||>)       p           q          =  p  ||| q

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

transpose ((A 'a' ||| B 5 ||| A 'n')   <|||>  
             (A 'o' ||| B 3 ||| A 'p') <|||>
            (A 'i' ||| B 0 ||| A 'l'))

Но когда я запускаю программу с "моей" функцией списка и несовершенной пользовательской функцией транспонирования, компилятор не Пожаловаться. Я думал, что это связано с ленью. Может ли это быть проблемой? Спасибо за помощь.

Answer 1

Возможно, вы можете сделать это динамически

zwh :: [[a]] -> [a]
zwh xss = if any ((== 0) . length) xss then []
                                       else hs ++ zwh ts
          where
          (hs,ts) = foldr (\(hs',ts') (rs,qs) -> (hs':rs,ts':qs)) ([],[]) hts
          hts     = (,) <$> head <*> tail <$> xss

λ> zwh [[1,2,3],[4,5,6],[7,8,9]]
[1,4,7,2,5,8,3,6,9]
λ> zwh [[1,2],[4,5,6],[7,8,9]]
[1,4,7,2,5,8]

или в зависимости от типа a, если все в порядке, чтобы включить ограничение EQ a =>, оно еще более упрощается до

zwh :: Eq a => [[a]] -> [a]
zwh xss = if any (== []) xss then []
                             else hs ++ zwh ts
          where
          (hs,ts) = foldr (\(hs',ts') (rs,qs) -> (hs':rs,ts':qs)) ([],[]) hts
          hts     = (,) <$> head <*> tail <$> xss

Answer 2

После редактирования, я думаю, вы хотите что-то подобное? Как уже упоминалось в Чи в комментарии, это сбивает с толку, поскольку кажется, что (|||) является ассоциативным, что, возможно, является ядром проблемы, с которой вы сталкиваетесь. Если она ассоциативна, то базовая структура является (непустой-) похожей на список, поэтому мы знаем, как взять их транспонирование и легко склеить вместе и т. Д. c. Но если это не ассоциативно, то представление вместо этого является древовидным, и я не думаю, что вы можете канонически отображать / переносить деревья (например, делает A 0 <> A 1 <> A 2 = (A 0 ||| A 1) ||| A 2 или A 0 ||| (A 1 ||| A 2)?, Что имеет значение, если (|||) не является ассоциативным).

import Control.Lens.Iso (iso, mapping, under)
import qualified Data.List.NonEmpty as NE
import Data.List.NonEmpty (NonEmpty)
import Data.Semigroup (sconcat)

instance Semigroup Function where
  (<>) = (|||)

transposeFuncs :: NonEmpty Function -> Function
transposeFuncs = sconcat . under (mapping $ iso reify reflect) NE.transpose
  where
    reflect :: Function -> NonEmpty (Either Char Int)
    reflect (a ||| b) = reflect a <> reflect b
    reflect (A a)     = pure $ Left  a
    reflect     (B b) = pure $ Right b
    reify :: NonEmpty (Either Char Int) -> Function
    reify = sconcat . NE.map (either A B)

transposeFuncs $ NE.fromList 
  [ A 'a' ||| B  5  ||| A 'n'
  , A 'o' ||| B  3  ||| A 'p'
  , A 'i' ||| B  0  ||| A 'l'
  ]
  ==  A 'a' ||| A 'o' ||| A 'i'
  ||| B  5  ||| B  3  ||| B  0
  ||| A 'n' ||| A 'p' ||| A 'l' 

РЕДАКТИРОВАТЬ: Если вы хотите express ассоциативность в типе данных, то вы будете использовать что-то вроде следующего. Посмотрите, насколько лучше, когда типы соответствуют цели; каждое (semanti c) значение имеет только одно представление. Если бы вы позволили личность, тогда она была бы еще чище.

import Control.Lens (makeWrapped, mapping, under, _Unwrapped')
import Data.List.NonEmpty (NonEmpty, transpose)
import Data.Semigroup (sconcat)

data FuncAtom
  = A Char
  | B Int

newtype Function
  = FCompose (NonEmpty FuncAtom)
  deriving Semigroup via NonEmpty FuncAtom
makeWrapped ''Function

transposeFuncs :: NonEmpty Function -> Function
transposeFuncs = sconcat . under (mapping _Unwrapped') transpose