Reusing lists in patterns

Question

When I write:

sort [x] = [x]

Is the compiler smart enough to reuse the same list, or do I have to be explicit about it?

sort xs@[_] = xs

Zumstein

Answer 1

Is it smart enough? Let's see!

ezyang@javelin:~$ cat Foo.hs
module Foo where
foo [x] = [x]

Here is the STG:

ezyang@javelin:~$ ghc --make Foo.hs -ddump-stg -fforce-recomp
[1 of 1] Compiling Foo              ( Foo.hs, Foo.o )

==================== STG syntax: ====================
Foo.foo =
    \r srt:(0,*bitmap*) [ds_sdP]
        let-no-escape {
          fail_sdO =
              sat-only \r srt:(0,*bitmap*) [ds1_sdN]
                  Control.Exception.Base.patError "Foo.hs:2:0-12|function foo";
        } in 
          case ds_sdP of wild_sdY {
            [] -> fail_sdO GHC.Prim.realWorld#;
            : x_sdV ds1_sdT ->
                case ds1_sdT of wild1_sdZ {
                  [] -> : [x_sdV GHC.Types.[]];
                  : ipv_se0 ipv1_se1 -> fail_sdO GHC.Prim.realWorld#;
                };
          };
SRT(Foo.foo): [Control.Exception.Base.patError]

The interesting bit is this line:

                  [] -> : [x_sdV GHC.Types.[]];

where we see that we are creating a new cons-cell for x_sdV and []. So, no. However, this is not too bad, because x_sdV itself is shared, so it’s only a single constructor; furthermore, we are forcing the spine of the list xs, so GHC would need to rewrite it anyway. So don't worry about it.

Kulda

+1 I have absolutely no idea what I'm seeing here, but it sure looks impressive! – Zumstein

Yeah, STG is a bit funny to read. : indicates cons, and [x1 x2 x3] indicate the arguments to cons (there are two, since cons takes two arguments.) – Kulda