Создать список списков для каждого возможного-изменение-изменение списка

#haskell

Вопрос:

Прошу прощения за то, что не смог правильно сформулировать этот вопрос в названии; Я уже задавал тот же вопрос о тройках и решил все-таки выбрать список, так что вот объяснение. Спасибо за терпение и большую помощь, полученную здесь!

Мне нужно создать функцию, которая способна выполнять следующее, но я новичок в Haskell и нуждаюсь в передаче состояний, которые просто не входят в функциональную парадигму (и я не хочу полуимперативного решения, я просто хочу знать, как это сделать функциональным способом). Функциональность заключается в следующем:

 specialFunc :: [a] -> a -> [[a]]
specialFunc [1,2,3] 0
=> [[0,2,3],[1,0,3],[1,2,0]]

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

1. Что вы пробовали, что с этим не работает?

2. @WillemVanOnsem Моей первоначальной мыслью было использовать zip [0..] для перечисления элементов вспомогательную функцию specialFunc' , которая отображается поверх списка, и в этой функции использовать индекс для объединения всех элементов перед индексом, элемента, который необходимо вставить, и всех элементов после индекса. Однако это кажется немного странным способом решения проблемы.

Ответ №1:

Вы можете определить это рекурсивным способом. Если список пуст (1), то вы возвращаете пустой список, поэтому [] сопоставляется [] . Если список непустой (2), то мы создаем список, в котором первый элемент является хвостом непустого списка, перед которым добавляется значение, и мы повторяем в хвосте списка, и нужно добавить начало списка.

Таким образом, мы можем определить функцию, которая выглядит как:

 specialFunc :: [a] -> a -> [[a]]
specialFunc xs x = go xs
    where go [] = …      -- (1)
          go (h:hs) = …  -- (2)

Вы можете использовать map :: (a -> b) -> [a] -> [b] для добавления значения h к спискам, которые вы создаете с помощью рекурсии.

1. Большое вам спасибо, это действительно помогает!

2. Чтобы я правильно понял; значение h может иметь длину больше 1, верно? В данном примере с [1,2,3] вводом в качестве входных данных нам нужно будет добавить [1,2] к последнему, или я ошибаюсь? Теперь мой код: ... where go [] = [] go (h:hs) = (x:hs):go hs .

3. Вам нужно выполнить постобработку рекурсии, поэтому go hs требуется дополнительная обработка, вам нужно добавить каждый подсписок в go hs с h в качестве первого элемента.

Ответ №2:

Решение, с множеством благодарностей @WillemVanOnsem:

 specialFunc :: [a] -> a -> [[a]]
specialFunc xs x = go xs
    where go []     = []
          go (h:hs) = (x:hs): map (h:) (go hs)

Ответ №3:

Просто чтобы дать вам еще одно представление о том, как это можно сделать, вы можете включить ParallelListComp расширение и соответствующим образом заархивировать результат inits и tails :

 {-# Language ParallelListComp #-}
import Data.List
specialFunc xs x = [pre    [x]    suf | pre <- inits xs | _:suf <- tails xs]

Конечно, ту же идею можно реализовать и без расширения, хотя я думаю, что это не так красиво:

 import Data.List
specialFunc xs x = zipWith (pre suf -> pre    [x]    suf) (inits xs) (tail (tails xs))