Блог

Я пытаюсь понять следующую проблему: я определил список, и я использую функцию fold в этом списке для объединения этих строк.

с foldr

 food = ["Pizza", "Apple", "Banana"]
let f = (a b -> take 3 a    b)
foldr f "" food
-- result
"PizAppBan"
  

в то время как с foldl

 food = ["Pizza", "Apple", "Banana"]
    let f = (a b -> take 3 a    b)
    foldr f "" food
    -- result
    "BanAppPiz"
  

Итак, я понял, что порядок меняется, потому что, когда мы выполняем какую-то коммутативную операцию, порядок не важен … для конкатенации строк вместо этого.
итак, вопрос в том, как в fold left оценивается конкатенация строк и как я могу концептуально визуализировать порядок операций? потому что, если я выполняю шаг за шагом следующую операцию, результат процесса всегда будет одинаковым…

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

Порядок параметров функции свертки «перевернут». Действительно, если мы посмотрим на определения для foldl и foldr мы увидим:

 foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b  

Здесь в обоих определениях «накопитель» имеет тип b . Но, как вы можете видеть, в foldl функции функция fold имеет тип b -> a -> b , поэтому первым параметром является накопитель, вторым — элемент, и он возвращает новое значение для накопителя. Это иллюстрирует, что свертка выполняется слева направо.

Для функции foldr функция fold имеет тип a -> b -> b , поэтому сначала она принимает элемент, затем принимает значение для аккумулятора после сворачивания остальной части списка, и вы должны вернуть новое значение для аккумулятора. Таким образом, он складывается справа налево.

Если вы хотите, чтобы это работало foldl , вы, таким образом, используете b a -> … b аккумулятор. В этом случае вы возвращаетесь b take a 3 , поэтому мы добавляем первые три символа a в правый конец аккумулятора:

 Prelude> foldr (a b -> take 3 a    b) "" ["Pizza", "Apple", "Banana"]
"PizAppBan"
Prelude> foldl (b a -> b    take 3 a) "" ["Pizza", "Apple", "Banana"]
"PizAppBan"
  

Таким образом, переключения параметров недостаточно. Вычисление выполняется слева направо в случае foldl и справа налево в случае foldr , таким образом, это означает, что вам также необходимо поменять способ объединения.

Однако этот foldl вариант здесь будет менее эффективным, поскольку ( ) :: [a] -> [a] -> [a] функция занимает время, линейное по длине первого операнда.

Функция a b -> take 3 a b не является ни коммутативной, ни ассоциативной. Действительно, коммутативное означает, что f x y равно f y x для каждого x и y . Но если мы вызываем f "foobar" "qux" , мы получаем:

 Prelude> f "foobar" "qux"
"fooqux"
Prelude> f "qux" "foobar"
"quxfoobar"
  

Операция concat ( ) также не является коммутативной.

Кроме того, сопоставление также не является ассоциативным из-за take 3 части. Действительно, ассоциативная операция означает, что f x (f y z) равно f (f x y) z для каждого x , y и z . Но мы видим:

 Prelude> f (f "foo" "bar") "qux"
"fooqux"
Prelude> f "foo" (f "bar" "qux")
"foobarqux"
  

Однако, если вы сначала выполните a map , чтобы взять первые три символа каждой строки, тогда действительно порядок не имеет значения:

 Prelude> foldl (  ) "" (map (take 3) food)
"PizAppBan"
Prelude> foldr (  ) "" (map (take 3) food)
"PizAppBan"
  

Таким take 3 образом, часть делает функцию неассоциативной, и поэтому вы не можете использовать ее в обоих foldl и foldr без ее правильной адаптации.