Если у меня есть рекурсивный ADT
data MyType = A | B | C MyType | D MyType MyType
Я мог бы написать функцию, чтобы определить, содержит ли экземпляр MyType a A так:
hasA :: MyType -> Bool
hasA A = True
hasA B = False
hasA (C x) = hasA x
hasA (D x y) = (hasA x) || (hasA y)
Это будет работать для ациклических экземпляров, но оно не останавливается для циклических структур, например.
let x = C x in hasA x
Вместо этого в этом примере он должен вернуться False. В других случаях (используя D) он ошибочно не останавливается, а не возвращает True.
Итак, вопрос в том, как наиболее легко писать такие функции, как hasA, которые работают над циклическими структурами? Racket имеет особенно приятную функцию для этого в виде define/fix, что позволяет вам выполнять функцию типа hasA, как и предполагалось, и возвращать False для структуры в примере выше, с едва ли дополнительным кодом. Есть ли способ сделать что-то подобное в Haskell? Есть ли расширение для него?
Изменить: теперь я обнаружил, что define/fix на самом деле макрос, созданный Matt Might, который использует возможности метапрограммирования Racket, в особенности, но это не делает его менее важной особенностью Racket. Может быть, этот макрос можно воспроизвести в Haskell?
