Y combinator: Difference between revisions

=={{header|Dhall}}==

Dhall is not a turing complete language, so there's no way to implement the real Y combinator. That being said, you can replicate the effects of the Y combinator to any arbitrary but finite recursion depth using the builtin function Natural/Fold, which acts as a bounded fixed-point combinator that takes a natural argument to describe how har to recurse.

Here's an example using Natural/Fold to define recursive definitions of fibonacci and factorial:

<lang Dhall>let const

: ∀(b : Type) → ∀(a : Type) → a → b → a

= λ(r : Type) → λ(a : Type) → λ(x : a) → λ(y : r) → x

let fac

: ∀(n : Natural) → Natural

= λ(n : Natural) →

let factorial =

λ(f : Natural → Natural → Natural) →

λ(n : Natural) →

λ(i : Natural) →

if Natural/isZero i then n else f (i * n) (Natural/subtract 1 i)

in Natural/fold

n

(Natural → Natural → Natural)

factorial

(const Natural Natural)

1

n

let fib

: ∀(n : Natural) → Natural

= λ(n : Natural) →

let fibFunc = Natural → Natural → Natural → Natural

let fibonacci =

λ(f : fibFunc) →

λ(a : Natural) →

λ(b : Natural) →

λ(i : Natural) →

if Natural/isZero i

then a

else f b (a + b) (Natural/subtract 1 i)

in Natural/fold

n

fibFunc

fibonacci

(λ(a : Natural) → λ(_ : Natural) → λ(_ : Natural) → a)

0

1

n

in [fac 50, fib 50]</lang>

The above dhall file gets rendered down to:

<lang Dhall>[ 30414093201713378043612608166064768844377641568960512000000000000

, 12586269025

]</lang>