This is the terminology distinction fmap is noting with "We really don't have a good terminology for distinguishing between efficient constructive proofs (those

This is the terminology distinction fmap is noting with "We really don't have a good terminology for distinguishing between efficient constructive proofs (those corresponding to efficient algorithms) and inefficient ones...". The PDF calls the proof non-constructive in that it does not provide an efficient algorithm; however, fmap calls it constructive in that it does provide an inefficient algorithm.