У меня есть тип данных
data N a = N a [N a]
розовых деревьев и аппликативный экземпляр
instance Applicative N where
pure a = N a (repeat (pure a))
(N f xs) <*> (N a ys) = N (f a) (zipWith (<*>) xs ys)
и нужно доказать для нее Аппликативные законы. Однако чистое создает бесконечно глубокие, бесконечно ветвящиеся деревья. Так, например, доказав закон гомоморфизма
pure f <*> pure a = pure (f a)
Я думал, что доказательство равенства
zipWith (<*>) (repeat (pure f)) (repeat (pure a)) = repeat (pure (f a))
по приближению (или взятию) леммы. Однако мои попытки приводят к "порочным кругам" на индуктивном этапе. В частности, уменьшение
approx (n + 1) (zipWith (<*>) (repeat (pure f)) (repeat (pure a))
дает
(pure f <*> pure a) : approx n (repeat (pure (f a)))
где ап - аппроксимационная функция. Как я могу доказать равенство без явного коиндуктивного доказательства?