{
  "id": "enwiki-001377115289",
  "slug": "polymorphic-recursion",
  "title": "Polymorphic recursion",
  "qid": "",
  "lead": "In computer science, polymorphic recursion (also referred to as Milner&ndash;Mycroft typability or the Milner&ndash;Mycroft calculus) refers to a recursive parametrically polymorphic function where the type parameter changes with each recursive invocation made, instead of staying constant. Type inference for polymorphic recursion is equivalent to semi-unification and therefore undecidable and requires the use of a semi-algorithm or programmer-supplied type annotations.",
  "body": "In computer science, polymorphic recursion (also referred to as Milner&ndash;Mycroft typability or the Milner&ndash;Mycroft calculus) refers to a recursive parametrically polymorphic function where the type parameter changes with each recursive invocation made, instead of staying constant. Type inference for polymorphic recursion is equivalent to semi-unification and therefore undecidable and requires the use of a semi-algorithm or programmer-supplied type annotations. data Nested a = a : A length function defined over this datatype will be polymorphically recursive, as the type of the argument changes from Nested a to Nested [a] in the recursive call: length :: Nested a -> Int length Epsilon = 0 length (_ : Note that Haskell normally infers the type signature for a function as simple-looking as this, but here it cannot be omitted without triggering a type error. Richard Bird and Lambert Meertens (1998). \"Nested Datatypes\". C. Vasconcellos, L. Figueiredo, C. Camarao (2003). \"Practical Type Inference for Polymorphic Recursion: an Implementation in Haskell \". Journal of Universal Computer Science. L. Figueiredo, C. Camarao. \"Type Inference for Polymorphic Recursive Definitions: a Specification in Haskell\".",
  "categories": [
    "21493616",
    "23809257",
    "23888906",
    "26159830",
    "27436062",
    "31128806",
    "62213912",
    "7692542",
    "99587226"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1377115289",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1790545327.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001377115289",
    "type": "webpage",
    "title": "Polymorphic recursion",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/polymorphic-recursion",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          16
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          16
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001377115289",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1377115289",
    "note": "Immutable snapshot enwiki-001377115289"
  }
}