Re:Infinite work is less work
by lmm on Friday July 12, 2019 @04:58AM
(#20419293)
> True, but isn’t it also true that a catamorphism on any other data structure still operates one piece at a time? If so, I think this would imply that you _could_ concert your tree or whatever to an array and still get your result with Array#reduce.
No, the catamorphism operates on one part of the structure but that part of the structure is not necessarily (head, tail) like it is for reduce - rather it's the "base" shape of the recursive data structure.
E.g. it's easy to write a catamorphism on a tree that finds the maximum number of children any one node has. But if you flatten the tree into an array then it's obviously impossible to recover that information.
No, the catamorphism operates on one part of the structure but that part of the structure is not necessarily (head, tail) like it is for reduce - rather it's the "base" shape of the recursive data structure.
E.g. it's easy to write a catamorphism on a tree that finds the maximum number of children any one node has. But if you flatten the tree into an array then it's obviously impossible to recover that information.