Вставьте функцию используя foldl/foldr

Question

Я работал над отдельной функцией, которая возвращает список, который вставляет элемент x после каждого k элементов списка l (считая от конца списка). Например, отдельный (1, 0, [1,2,3,4]) должен возвращать [1,0,2,0,3,0,4]. Я закончил функцию, и она работает следующим образом:

fun separate (k: int, x: 'a, l: 'a list) : 'a list = 
  let
    fun kinsert [] _ = []
      | kinsert ls 0 = x::(kinsert ls k)
      | kinsert (l::ls) i = l::(kinsert ls (i-1))
  in
     List.rev (kinsert (List.rev l) k)
  end 

Сейчас я пытаюсь упростить функцию, используя foldl/foldr без какой-либо рекурсии, но я не могу заставить ее работать правильно. Любые советы / предложения о том, как подойти к этому? Благодарю вас!

Answer 1

Это более или менее мысли, которые у меня были, когда я пытался написать функцию, используя foldl/foldr:

• foldl/foldr абстрагирует рекурсию списка от логики, составляющей конечный результат.

• Начните с наброска функции, которая имеет структуру, очень похожую на исходную программу, но где foldr используется и kinsert вместо того, чтобы быть рекурсивной функцией, это функция, данная foldr:

  fun separate (k, x, L) =
      let fun kinsert (y, ys) = ...
      in foldr kinsert [] L
      end
  

  Это не строго необходимо; kinsert может также быть анонимным

• Вы используете внутреннюю вспомогательную функцию kinsert потому что вам нужна копия k (i) что вы постепенно уменьшаете и возвращаетесь к k каждый раз, когда он достигает 0. Так что в то время как список, который kinsert выплевывает эквивалентно накопленной переменной сгиба, i временно накапливается (и иногда сбрасывается) почти таким же образом.

• + Изменить kinsertНакапливается переменная, чтобы освободить место для i:

  fun separate (k, x, L) =
      let fun kinsert (y, (i, xs)) = ...
      in foldr kinsert (?, []) L
      end
  

  Теперь результат сгиба становится 'a * 'a list, что вызывает две проблемы: 1) Мы действительно только хотели накопить i временно, но это часть окончательного результата. Это можно обойти, отбросив его с помощью #2 (foldr ...), 2) Если результат теперь кортеж, я не уверен, что поставить в качестве первого i на месте ?,

• поскольку kinsert это отдельное объявление функции, вы можете использовать сопоставление с образцом и несколько тел функций:

  fun separate (k, x, L) =
      let fun kinsert (y, (0, ys)) = ...
            | kinsert (y, (i, ys)) = ...
      in ... foldr kinsert ... L
      end
  

• Ваш оригинал kinsert отклоняется от шаблона рекурсии, который складка выполняет одним способом: в среднем шаблоне, когда i Матчи 0вы не отрубаете элемент ls, который в противном случае вы бы заставили. Так что ваши 0 чехол будет немного отличаться от оригинала; вы, вероятно, столкнетесь с ошибкой.

• Помни что foldr фактически посещает последний элемент списка первым, после чего i будет иметь начальное значение, где с оригиналом kinsert, начальное значение для i будет, когда вы на первом элементе.

• В зависимости от того, используете ли вы foldl или же foldr вы столкнетесь с разными проблемами: foldl перевернет ваш список, но адрес элементов в правильном порядке. foldr сохранит правильный порядок в списке, но при создании другого результата k не делит длину L...

• На этом этапе рассмотрите возможность использования foldl и вместо этого переверните список:

  fun separate (k, x, L) =
      let fun kinsert (y, (?, ys)) = ...
            | kinsert (y, (i, ys)) = ...
      in rev (... foldl kinsert ... L)
      end
  

  В противном случае вы начнете замечать, что separate (2, 0, [1,2,3,4,5]) должно дать [1,2,0,3,4,0,5] и не [1,0,2,3,0,5],