Блог

что делает эта функция в Haskel?

Я не понимаю, как здесь работает рекурсия

  f[]=[]
 f(x:xs)=x: [y|y <- f xs, x/=y]
  

 f[]=[]
f(x:xs) = x : [y|y <- f xs, x/=y]
  

Эта функция удаляет дубликаты из списка. Вот как это работает:

• В базовом случае список пуст, поэтому он возвращает пустой список.
• В противном случае вы берете первый элемент x и предполагаете (индуктивная гипотеза), который f xs дает вам список без дубликатов. Теперь единственное, что вам нужно сделать, это убедиться, что вы не вставляете x снова. Итак, сжатие списка означает: возьмите все остальные элементы (которые по индуктивной гипотезе уникальны), но удалите x .

Чувствует ли это прямо сейчас?

ps. вы можете записать второе предложение также как: f(x:xs) = x : filter (/= x) (f xs)

Мне кажется, что это устраняет любые повторяющиеся записи в списке.

Вот как это работает:

f[] = [] означает, что, когда вход представляет собой пустой список, на выходе будет пустой список.
Затем f(x:xs) = x: [y|y <- f xs, x/=y] использует то, что называется пониманием списка. Он берет начало входного списка, а затем добавляет понимание списка.

Понимание списка выглядит следующим образом: «y такое, что y находится в f (xs), а y не равно x»

Итак, это список элементов в f(xs), которые не равны элементу head .