Zip со значением по умолчанию вместо сброса значений?
Я ищу функцию в haskell, чтобы сжать два списка, которые могут различаться по длине.
Все функции zip, которые я мог найти, просто отбрасывают все значения одного списка, который длиннее другого.
Например: в моем упражнении у меня есть два списка примеров.
Если первый короче второго, я должен заполнить, используя 0. В противном случае я должен использовать 1.
Мне не разрешено использовать любую рекурсию. Я просто должен использовать функции более высокого порядка.
Есть ли какая-нибудь функция, которую я могу использовать?
Я действительно не мог найти никакого решения до сих пор.
10 ответов
Вы можете добавить в каждый список список из 0 или 1, а затем взять нужное число из сжатого списка результатов:
zipWithDefault :: a -> b -> [a] -> [b] -> [(a,b)]
zipWithDefault da db la lb = let len = max (length la) (length lb)
la' = la ++ (repeat da)
lb' = lb ++ (repeat db)
in take len $ zip la' lb'
У этой проблемы есть некоторая структура, и вот она. Я буду использовать этот материал:
import Control.Applicative
import Data.Traversable
import Data.List
Прежде всего, списки с отступом - это полезная концепция, поэтому давайте найдем для них тип.
data Padme m = (:-) {padded :: [m], padder :: m} deriving (Show, Eq)
Далее я помню, чтоzip операция порождает Applicative Например, в библиотеке как newtype ZipList (популярный пример неMonad). Applicative ZipList равносильно украшению моноида, заданного бесконечностью и минимумом. Padme имеет аналогичную структуру, за исключением того, что его лежащий в основе моноид положительные числа (с бесконечностью), используя один и максимум.
instance Applicative Padme where
pure = ([] :-)
(fs :- f) <*> (ss :- s) = zapp fs ss :- f s where
zapp [] ss = map f ss
zapp fs [] = map ($ s) fs
zapp (f : fs) (s : ss) = f s : zapp fs ss
Я обязан произнести обычное заклинание, чтобы сгенерировать дефолт Functor пример.
instance Functor Padme where fmap = (<*>) . pure
Таким образом, мы можем уйти! Например, функция, которая берет рваный список строк и дополняет их пробелами, становится одной строкой.
deggar :: [String] -> [String]
deggar = transpose . padded . traverse (:- ' ')
Увидеть?
*Padme> deggar ["om", "mane", "padme", "hum"]
["om ","mane ","padme","hum "]
Это можно выразить, используя These("представляет значения с двумя неисключительными возможностями") и Align ("функторы, поддерживающие операцию zip, которая принимает объединение неоднородных фигур") из этой библиотеки:
import Data.Align
import Data.These
zipWithDefault :: Align f => a -> b -> f a -> f b -> f (a, b)
zipWithDefault da db = alignWith (fromThese da db)
salign а другой специализированный выравнивает в Data.Align Также стоит взглянуть на.
Благодаря u/WarDaft, u/gallais и u/sjakobi из r/haskell за указание на этот ответ должны существовать здесь.
Это должно сделать трюк:
import Data.Maybe (fromMaybe)
myZip dx dy xl yl =
map (\(x,y) -> (fromMaybe dx x, fromMaybe dy y)) $
takeWhile (/= (Nothing, Nothing)) $
zip ((map Just xl) ++ (repeat Nothing)) ((map Just yl) ++ (repeat Nothing))
main = print $ myZip 0 1 [1..10] [42,43,44]
В основном, добавить бесконечный список Nothing в конец обоих списков, затем сжать их и отбросить результаты, когда оба Nothing, Затем замените Nothings с соответствующим значением по умолчанию, отбрасывая больше не нужно Justпока ты на этом.
Нет length, не считая, не рекурсии ручной работы, не сотрудничающие сгибы. transpose делает трюк:
zipLongest :: a -> b -> [a] -> [b] -> [(a,b)]
zipLongest dx dy xs ys = map head . transpose $ -- longest length;
[ -- view from above
zip xs
(ys ++ repeat dy) -- with length of xs
, zip (xs ++ repeat dx)
ys -- with length of ys
]
Результат transpose это такой же длинный список, как и самый длинный в его входном списке списков. map head берет первый элемент в каждом "столбце", то есть ту пару, которая нам нужна, какой бы ни был самый длинный список.
(обновление:) Для списков эффективное заполнение до максимальной длины - с целью избежать потенциально квадратичного поведения других последовательно- комбинированных подходов - может следовать той же идее:
padAll :: [[a]] -> a -> [[a]]
padAll xs c = transpose $
zipWith const
(transpose [x ++ repeat c | x <- xs]) -- pad all, and cut
(takeWhile id . map or . transpose $ -- to the longest list
[ (True <$ x) ++ repeat False | x <- xs])
> mapM_ print $ padAll ["ommmmmmm", "ommmmmm", "ommmmm", "ommmm", "ommm", "omm",
"om", "o"] '-'
"ommmmmmm"
"ommmmmm-"
"ommmmm--"
"ommmm---"
"ommm----"
"omm-----"
"om------"
"o-------"
Вам не нужно сравнивать длины списка. Попытайтесь представить свою почтовую функцию как функцию, принимающую только один аргумент xs и возвращая функцию, которая будет принимать ys и выполните необходимый почтовый индекс. Затем попробуйте написать рекурсивную функцию, которая xs только следующим образом.
type Result = [Int] -> [(Int,Int)]
myZip :: [Int] -> Result
myZip [] = map (\y -> (0,y)) -- :: Result
myZip (x:xs) = f x (myZip xs) -- :: Result
where f x k = ??? -- :: Result
Как только вы нашли f, обратите внимание, что вы можете превратить рекурсию выше в складку!
Вот еще одно решение, которое работает с бесконечными списками и представляет собой простое обновление zip-функций Prelude:
zipDefault :: a -> b -> [a] -> [b] -> [(a,b)]
zipDefault _da _db [] [] = []
zipDefault da db (a:as) [] = (a,db) : zipDefault da db as []
zipDefault da db [] (b:bs) = (da,b) : zipDefault da db [] bs
zipDefault da db (a:as) (b:bs) = (a,b) : zipDefault da db as bs
а также
zipDefaultWith :: a -> b -> (a->b->c) -> [a] -> [b] -> [c]
zipDefaultWith _da _db _f [] [] = []
zipDefaultWith da db f (a:as) [] = f a db : zipDefaultWith da db f as []
zipDefaultWith da db f [] (b:bs) = f da b : zipDefaultWith da db f [] bs
zipDefaultWith da db f (a:as) (b:bs) = f a b : zipDefaultWith da db f as bs
@pigworker, спасибо за ваше просветительское решение!
Еще одна реализация:
zipWithDefault :: a -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
zipWithDefault dx _ f [] ys = zipWith f (repeat dx) ys
zipWithDefault _ dy f xs [] = zipWith f xs (repeat dy)
zipWithDefault dx dy f (x:xs) (y:ys) = f x y : zipWithDefault dx dy f xs ys
А также:
zipDefault :: a -> b -> [a] -> [b] -> [c]
zipDefault dx dy = zipWithDefault dx dy (,)
Как ты сам сказал, стандарт zip :: [a] -> [b] -> [(a, b)] удаляет элементы из длинного списка. Чтобы исправить этот факт, вы можете изменить свой вклад, прежде чем дать его zip, Сначала вам нужно выяснить, какой список является более коротким (скорее всего, используя length). Например,
zip' x xs y ys | length xs <= length ys = ...
| otherwise = ...
где x это значение по умолчанию для более коротких xs а также y значение по умолчанию для более коротких ys,
Затем вы расширяете более короткий список желаемыми элементами по умолчанию (достаточно, чтобы учесть дополнительные элементы другого списка). Удобный трюк для этого без необходимости знать длину более длинного списка - использовать функцию repeat :: a -> [a] это повторяет его аргумент бесконечно часто.
zip' x xs y ys | length xs <= length ys = zip {-do something with xs-} ys
| otherwise = zip xs {-do something with ys-}
Я хотел бы обратиться ко второй части решения Уилла Несса, в котором прекрасно используются известные функции, предоставив еще один ответ на исходный вопрос.
zipPadWith :: a -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
zipPadWith n _ f [] l = [f n x | x <- l]
zipPadWith _ m f l [] = [f x m | x <- l]
zipPadWith n m f (x:xs) (y:ys) = f x y : zipPadWith n m f xs ys
Эта функция дополнит список выбранным элементом. Вы можете использовать список одного и того же элемента, повторяющийся столько раз, сколько списков в другом, например:
rectangularWith :: a -> [[a]] -> [[a]]
rectangularWith _ [] = []
rectangularWith _ [ms] = [[m] | m <- ms]
rectangularWith n (ms:mss) = zipPadWith n [n | _ <- mss] (:) ms (rectangularWith n mss)
Конечным результатом будет транспонированный прямоугольный список списков, дополненный предоставленным нами элементом, поэтому нам нужно только импортироватьtransposeотData.Listи восстановить порядок элементов.
mapM_ print $ transpose $ rectangularWith 0 [[1,2,3,4],[5,6],[7,8],[9]]
[1,2,3,4]
[5,6,0,0]
[7,8,0,0]
[9,0,0,0]