Skip to content

GitLab

Open
Opened by Neo@nmichael44

Linear search when compiling case expression on Integers

When compiling a function like the following:

h' :: Integer -> Integer 
h' 7 = 1
h' 6 = 10
h' 5 = 100
h' 4 = 1000
h' 3 = 10000
h' 2 = 100000
h' 1 = 1000000
h' 0 = 10000000
h' _ = 2

we generate the following core:

h'
  = \ (ds_d7A1 :: Integer) ->
      case integer-gmp-1.0.2.0:GHC.Integer.Type.eqInteger#
             ds_d7A1 Magic2.h'6
      of {
        __DEFAULT ->
          case integer-gmp-1.0.2.0:GHC.Integer.Type.eqInteger#
                 ds_d7A1 Magic2.h'5
          of {
            __DEFAULT ->
              case integer-gmp-1.0.2.0:GHC.Integer.Type.eqInteger#
                     ds_d7A1 Magic2.h'4
              of {
                __DEFAULT ->
                  case integer-gmp-1.0.2.0:GHC.Integer.Type.eqInteger#
                         ds_d7A1 Magic2.h'3
                  of {
                    __DEFAULT ->
                      case integer-gmp-1.0.2.0:GHC.Integer.Type.eqInteger#
                             ds_d7A1 Magic2.h'2
                      of {
                        __DEFAULT ->
                          case integer-gmp-1.0.2.0:GHC.Integer.Type.eqInteger#
                                 ds_d7A1 Magic2.h9
                          of {
                            __DEFAULT ->
                              case integer-gmp-1.0.2.0:GHC.Integer.Type.eqInteger#
                                     ds_d7A1 Magic2.h1
                              of {
                                __DEFAULT ->
                                  case integer-gmp-1.0.2.0:GHC.Integer.Type.eqInteger#
                                         ds_d7A1 Magic2.h'1
                                  of {
                                    __DEFAULT -> Magic2.h9;
                                    1# -> Magic2.h8
                                  };
                                1# -> Magic2.h7
                              };
                            1# -> Magic2.h6
                          };
                        1# -> Magic2.h5
                      };
                    1# -> Magic2.h4
                  };
                1# -> Magic2.h3
              };
            1# -> Magic2.h2
          };
        1# -> Magic2.h1
      }

So we linearly go through the list of integers. There is really no good reason why we couldn't do binary search here (like we do if Integer is changed to Int).