Замены определяют

Question

Я пытаюсь получить программу, которая предоставляет все возможные способы замены компонента на новый, основанный на новом компоненте и списке. Моя цель - написать что-то простое, например:

max3 :: Ord a => a -> a -> a -> a
max3 a b c
      | a > b && a > c = a
      | b > a && b > c = b
      | c > a && c > b = c
      | otherwise = error "."

Например:

replacements :: a -> [a] -> [[a]]
replacements 'x' "abc" == ["xbc","axc","abx"]
replacements 1 [] == []

Answer 1

Вот один из способов написания replacements:

replacements :: a -> [a] -> [[a]]
replacements _ [] = []
replacements x (y:ys) = (x:ys) : map (y:) (replacements x ys)

Чтобы понять рекурсию, это можно написать более многословно, например:

replacements :: a -> [a] -> [[a]]
replacements _ [] = []
replacements x (y:ys) =
  let first = x:ys
      recur = replacements x ys
      rest = map (\x_with_ys -> y:x_with_ys) recur
  in first : rest

Оценка первого из них путемhand for replacements 'x' "abc":

   replacements 'x' "abc"
~> ('x':"bc") : map ('a':) (replacements 'x' "bc")
~> "xbc" : map ('a':) (('x':"c") : map ('b':) (replacements 'x' "c"))
~> "xbc" : map ('a':) ("xc" : map ('b':) (('x':[]) : map ('c':) (replacements 'x' "")))
~> "xbc" : map ('a':) ("xc" : map ('b':) ("x" : map ('c':) []))
~> "xbc" : map ('a':) ("xc" : map ('b':) ("x" : []))
~> "xbc" : map ('a':) ("xc" : map ('b':) ["x"])
~> "xbc" : map ('a':) ("xc" : ["bx"])
~> "xbc" : map ('a':) ["xc", "bx"]
~> "xbc" : ["axc", "abx"]
~> ["xbc", "axc", "abx"]

Как намекал Уилл Несс, вы можете выразить это с помощью функций высшего порядка, а не явной рекурсии. Чтобы уточнить подсказку Уилла, попробуйте поиграть с inits и tails:

λ> import Data.List
λ> inits "abc"
["","a","ab","abc"]
λ> tails "abc"
["abc","bc","c",""]
λ> zip (inits "abc") (tails "abc")
[("","abc"),("a","bc"),("ab","c"),("abc","")]

Затем посмотрите на zipWith. (Некоторое освещение в LYAH .)

---

Я также не знаю, что max3 имеет отношение к этой проблеме, но другой способ написать max3:

max3 :: Ord a => a -> a -> a -> a
max3 a b c = max a (max b c)