# Reduction stack overflow

**URL:** <https://discourse.haskell.org/t/reduction-stack-overflow/10193>\
**Category:** Learn\
**Created:** [August 19, 2024, 9:57am UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193 "2024-08-19T09:57:23Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![marcosh](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/marcosh/32/436_2.png) [@marcosh](https://discourse.haskell.org/u/marcosh)\
**Post date:** [August 19, 2024, 9:57am UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/1 "2024-08-19T09:57:23Z")

</div>

Consider this snippet of code

```haskell
{-# LANGUAGE QuantifiedConstraints #-}

module Foo where

import Control.Monad.Writer

data Foo = Foo

foo :: (forall e. Monoid e => MonadWriter e (m e)) => m [Foo] Int
foo = pure 1

```

It produces an error

```haskell
Reduction stack overflow; size = 201
When simplifying the following type: Monoid [Foo]

```

See [here](https://play.haskell.org/saved/qbfEaI5T) if you want to play with it.

Am I wrong or the compiler is telling me that it is not able to find an instance `Monoid [Foo]`?

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [August 19, 2024, 11:17am UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/2 "2024-08-19T11:17:29Z")

</div>

Some of the articles found during a brief websearch using `ghc haskell "reduction stack" increase` mention this option:

```nohighlight
Use -freduction-depth=0 to disable this check
(any upper bound you could choose might fail unpredictably with
minor updates to GHC, so disabling the check is recommended if
you're sure that type checking should terminate)

```

On my system:

```nohighlight
# ghci -freduction-depth=0 Foo.hs
GHCi, version 9.8.2: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling Foo ( Foo.hs, interpreted )

```

…and still going. So what happens when you use `-freduction-depth=0` ?

---

<div class="post-metadata">

**Author:** ![marcosh](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/marcosh/32/436_2.png) [@marcosh](https://discourse.haskell.org/u/marcosh)\
**Post date:** [August 19, 2024, 12:32pm UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/3 "2024-08-19T12:32:44Z")

</div>

It would seem strange to me that this is a case of not enough room for recursion, since there is no recursive type involved.

It just looks like ghc is not able to find the `Monoid [a]` instance.

Btw, just running `ghci -freduction-depth=0 Foo.hs` just keeps going…

---

<div class="post-metadata">

**Author:** ![adamgundry](https://avatars.discourse-cdn.com/v4/letter/a/34f0e0/32.png) [@adamgundry](https://discourse.haskell.org/u/adamgundry)\
**Post date:** [August 19, 2024, 12:42pm UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/4 "2024-08-19T12:42:08Z")

</div>

I think this program indeed yields an infinite loop in the constraint solver. The issue is that `MonadWriter e (m e)` has `Monoid e` as a superclass, so when GHC tries to solve the `Applicative (m [Foo])` constraint arising from `pure`:

- It can use the quantified constraint to get `MonadWriter [Foo] (m [Foo])` (and hence `Monad (m [Foo])` and hence `Applicative (m [Foo])`), if only it can solve `Monoid [Foo]`.
- Now in order to produce `Monoid [Foo]`, rather than using the global instance, it foolishly decides to use the quantified constraint and take the superclass. But then it needs to solve `Monoid [Foo]` again, and the loop begins.

GHC really ought to at least require `UndecidableInstances` for this, but currently it fails to do so:

> **[\#22535: Regression: infinite loop on quantified constraints · Issues ·...](https://gitlab.haskell.org/ghc/ghc/-/issues/22535)**
>
> {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE QuantifiedConstraints #-}

---

<div class="post-metadata">

**Author:** ![marcosh](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/marcosh/32/436_2.png) [@marcosh](https://discourse.haskell.org/u/marcosh)\
**Post date:** [August 19, 2024, 12:50pm UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/5 "2024-08-19T12:50:08Z")

</div>

ah, that makes some sense, thanks for the explanation!

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [August 19, 2024, 3:01pm UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/6 "2024-08-19T15:01:15Z")

</div>

`UndecidableInstances` makes no difference here:

```nohighlight
# ghci -XUndecidableInstances -freduction-depth=0 Foo.hs
GHCi, version 9.8.2: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling Foo ( Foo.hs, interpreted )

```

---

<div class="post-metadata">

**Author:** ![darkxero](https://avatars.discourse-cdn.com/v4/letter/d/f07891/32.png) [@darkxero](https://discourse.haskell.org/u/darkxero)\
**Post date:** [August 19, 2024, 11:24pm UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/7 "2024-08-19T23:24:13Z")

</div>

> [@marcosh](#):
>
> See [here](https://play.haskell.org/saved/qbfEaI5T) if you want to play with it.

I noticed that switching the compiler version to 8.6.5 or 8.8.4 works.  
A regression then?

```haskell
foo :: (forall a. a, forall e. Monoid e => MonadWriter e (m e)) => m [Foo] Int
foo = pure 1

```

Compiles but I don’t know what it means.  
Also this compiles on 9.10.1 and 9.8.2 and 9.6.6 but not below.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [August 20, 2024, 12:11am UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/8 "2024-08-20T00:11:43Z")

</div>

It _compiles_ with GHC 9.8.2? Hmm:

- 

```nohighlight
# ghc -V
The Glorious Glasgow Haskell Compilation System, version 9.8.2

```

- 

```nohighlight
# ghc -c Foo.hs

Foo.hs:10:7: error: [GHC-40404]
    • Reduction stack overflow; size = 201
      When simplifying the following type: Monoid [Foo]
    • In the expression: pure 1
      In an equation for ‘foo’: foo = pure 1
    Suggested fix:
      Use -freduction-depth=0 to disable this check
      (any upper bound you could choose might fail unpredictably with
       minor updates to GHC, so disabling the check is recommended if
       you're sure that type checking should terminate)
   |
10 | foo = pure 1
   | ^^^^

```

- 

```nohighlight
# ghc -c -XUndecidableInstances Foo.hs

Foo.hs:10:7: error: [GHC-40404]
    • Reduction stack overflow; size = 201
      When simplifying the following type: Monoid [Foo]
    • In the expression: pure 1
      In an equation for ‘foo’: foo = pure 1
    Suggested fix:
      Use -freduction-depth=0 to disable this check
      (any upper bound you could choose might fail unpredictably with
       minor updates to GHC, so disabling the check is recommended if
       you're sure that type checking should terminate)
   |
10 | foo = pure 1
   | ^^^^

```

- 

```nohighlight
# ghc -c -freduction-depth=0 Foo.hs

^C
#

```

- 

```nohighlight
# ghc -c -XUndecidableInstances -freduction-depth=0 Foo.hs

^C
#

```

Regression or not, it’s certainly something that needs careful monitoring; [principle of least surprise](https://www.code4it.dev/cleancodetips/principle-of-least-surprise) and all…

---

<div class="post-metadata">

**Author:** ![rhendric](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/rhendric/32/2689_2.png) [@rhendric](https://discourse.haskell.org/u/rhendric)\
**Post date:** [August 20, 2024, 12:12am UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/9 "2024-08-20T00:12:00Z")

</div>

> [@darkxero](#):
>
> Compiles but I don’t know what it means.

It means you would never be able to use `foo`, as instantiating it would require a solution to every constraint ever dreamed up by machine or man.

A more effective workaround for this specific case would be

```hs
foo :: (Monoid [Foo], forall e. Monoid e => MonadWriter e (m e)) => m [Foo] Int
foo = pure 1

```

(You’ll get a compiler warning about a simplifiable class constraint—accurate, but you made me do this, GHC!)

---

<div class="post-metadata">

**Author:** ![simonpj](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/simonpj/32/890_2.png) [@simonpj](https://discourse.haskell.org/u/simonpj)\
**Post date:** [October 23, 2024, 8:20am UTC](https://discourse.haskell.org/t/reduction-stack-overflow/10193/10 "2024-10-23T08:20:16Z")

</div>

Interesting thread. I have opened a ticket [#25412: Superclasses of quantified constraints leads to solver loop · Issues · Glasgow Haskell Compiler / GHC · GitLab](https://gitlab.haskell.org/ghc/ghc/-/issues/25412), and added some diagnosis, for those who are interested.