Array indexing doesn't work when the index is a lambda parameter

[cgranade]

Describe the bug

When writing a lambda function (idx) -> perm[idx] for indexing into an array (similar to the standard library function LookupFunction), a confusing error message is returned in some cases.

To Reproduce

Attempt to compile the following code using dotnet build:

function Squared(perm : Int[]) : Int[] {
    return Mapped((idx) -> perm[idx], perm);
}

Expected behavior

Since (idx) -> perm[idx] is mapped over an array of type Int, the type of idx should be definitely known as Int, allowing the snippet above to compile.

Screenshots

At the console, a rather long dump is returned:

➜  dotnet build
Microsoft (R) Build Engine version 17.2.0-preview-22104-01+09bdfae16 for .NET
Copyright (C) Microsoft Corporation. All rights reserved.

  Determining projects to restore...
  All projects are up-to-date for restore.
  You are using a preview version of .NET. See: https://aka.ms/dotnet-support-policy
  Determining projects to restore...
  All projects are up-to-date for restore.
C:\...\OrderFinding.qs(29,37): error QS5003: Expecting an expression of type Int or Range. Got an expression of type 'c. [C:\...\OrderFinding.csproj]
  : info: 
  System.ArgumentException: Unsupported QsExpressionKind Lambda
    { kind = Function
      paramTuple =
                  QsTuple
                    (seq
                       [QsTupleItem
                          { VariableName = ValidName "idx"
                            Type =
                                  { kind = Int
                                    range =
                                           Inferred
                                             (Range
                                                (Position (0,15),Position (0,18))) }
                            InferredInformation =
                                                 { IsMutable = false
                                                   HasLocalQuantumDependency =
                                                                              false }
                            Position = Value (Position (1,8))
                            Range = Range (Position (0,15),Position (0,18)) }])
      body =
            { Expression =
                          ArrayItem
                            ({ Expression = Identifier (LocalVariable "perm",Null)
                               TypeArguments = seq []
                               ResolvedType =
                                             { kind =
                                                     ArrayType
                                                       { kind = Int
                                                         range =
                                                                Inferred
                                                                  (Range
                                                                     (Position
                                                                        (0,23),
                                                                      Position
                                                                        (0,27))) }
                                               range =
                                                      Inferred
                                                        (Range
                                                           (Position (0,23),
                                                            Position (0,27))) }
                               InferredInformation =
                                                    { IsMutable = false
                                                      HasLocalQuantumDependency =
                                                                                 false }
                               Range =
                                      Value
                                        (Range (Position (0,23),Position (0,27))) },
                             { Expression = Identifier (LocalVariable "idx",Null)
                               TypeArguments = seq []
                               ResolvedType =
                                             { kind = Int
                                               range =
                                                      Inferred
                                                        (Range
                                                           (Position (0,28),
                                                            Position (0,31))) }
                               InferredInformation =
                                                    { IsMutable = false
                                                      HasLocalQuantumDependency =
                                                                                 false }
                               Range =
                                      Value
                                        (Range (Position (0,28),Position (0,31))) })
              TypeArguments = seq []
              ResolvedType =
                            { kind = Int
                              range =
                                     Inferred
                                       (Range (Position (0,23),Position (0,27))) }
              InferredInformation = { IsMutable = false
                                      HasLocalQuantumDependency = false }
              Range = Value (Range (Position (0,23),Position (0,32))) } }
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchemaGeneric[TBondExpression,TBondSymbol,TBondType,TCompilerExpression,TCompilerSymbol,TCompilerType](QsExpressionKind`3 qsExpressionKind, Func`2 expressionTranslator, 
   Func`2 symbolTranslator, Func`2 typeTranslator)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsExpressionKind`3 qsExpressionKind)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(TypedExpression typedExpression)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.<>c__DisplayClass56_0`6.<ToBondSchemaGeneric>b__0(TCompilerExpression v)
     at System.Linq.Enumerable.SelectArrayIterator`2.ToList()
     at System.Linq.Enumerable.ToList[TSource](IEnumerable`1 source)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchemaGeneric[TBondExpression,TBondSymbol,TBondType,TCompilerExpression,TCompilerSymbol,TCompilerType](QsExpressionKind`3 qsExpressionKind, Func`2 expressionTranslator, 
   Func`2 symbolTranslator, Func`2 typeTranslator)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsExpressionKind`3 qsExpressionKind)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(TypedExpression typedExpression)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToQsExpressionKindExpressionDoubleGeneric[TBond,TCompiler](TCompiler expression1, TCompiler expression2, Func`2 typeTranslator)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchemaGeneric[TBondExpression,TBondSymbol,TBondType,TCompilerExpression,TCompilerSymbol,TCompilerType](QsExpressionKind`3 qsExpressionKind, Func`2 expressionTranslator, 
   Func`2 symbolTranslator, Func`2 typeTranslator)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsExpressionKind`3 qsExpressionKind)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(TypedExpression typedExpression)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsStatementKind qsStatementKind)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsStatement qsStatement)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.<>c.<ToBondSchema>b__32_0(QsStatement s)
     at System.Linq.Enumerable.SelectArrayIterator`2.ToList()
     at System.Linq.Enumerable.ToList[TSource](IEnumerable`1 source)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsScope qsScope)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToSpecializationImplementationKindProvided(QsTuple`1 tuple, QsScope implementation)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(SpecializationImplementation specializationImplementation)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsSpecialization qsSpecialization)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.<>c.<ToBondSchema>b__10_1(QsSpecialization s)
     at System.Linq.Enumerable.SelectArrayIterator`2.ToList()
     at System.Linq.Enumerable.ToList[TSource](IEnumerable`1 source)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsCallable qsCallable)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsNamespaceElement qsNamespaceElement)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.<>c.<ToBondSchema>b__24_0(QsNamespaceElement e)
     at System.Linq.Enumerable.SelectArrayIterator`2.ToList()
     at System.Linq.Enumerable.ToList[TSource](IEnumerable`1 source)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.ToBondSchema(QsNamespace qsNamespace)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.<>c.<CreateBondCompilation>b__0_0(QsNamespace n)
     at System.Linq.Enumerable.SelectArrayIterator`2.ToList()
     at System.Linq.Enumerable.ToList[TSource](IEnumerable`1 source)
     at Microsoft.Quantum.QsCompiler.BondSchemas.BondSchemaTranslator.CreateBondCompilation(QsCompilation qsCompilation)
     at Microsoft.Quantum.QsCompiler.BondSchemas.Protocols.SerializeQsCompilationToSimpleBinary(QsCompilation qsCompilation, Stream stream)
     at Microsoft.Quantum.QsCompiler.CompilationLoader.SerializeSyntaxTree(QsCompilation syntaxTree, Stream stream, Action`1 onException)

EXEC(1,1): error QS7106: Unable to serialize the built compilation. [C:\...\OrderFinding.csproj]

System information

<Project Sdk="Microsoft.Quantum.Sdk/0.23.195983">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>netcoreapp3.1</TargetFramework>
  </PropertyGroup>
</Project>

[bamarsha]

The serialization error is a separate issue (opened #1387 for that). The index error has the same root cause as an issue with array copy-and-update expressions:

let f = (n, i) -> [0, size = n] w/ i <- 1;
let _ = f(5, 0);

While the compiler is able to infer that f has type (Int, Int) -> Int[], it still shows an error for the usage of i:

Expecting an expression of type Int or Range. Got an expression of type 'b.

Type inference is applying the Indexed constraint too early, when the type of the array is known, but when the type of the index is not yet known.