# Zulip Chat Archive

## Stream: new members

### Topic: defining a list merge function

#### Scott Kovach (Dec 28 2020 at 19:04):

hi everyone, new Lean user here! I have some questions about this example:

```
def merge {α : Type} [linear_order α] : list α → list α → list α
| [] ys := ys
| xs [] := xs
| (x::xs) (y::ys) := if x ≤ y then x :: merge xs (y::ys) else y :: merge (x::xs) ys
--#reduce merge [1,3] [2]
example {α : Type} [linear_order α] (l₂ : list α) : l₂ = merge list.nil l₂ :=
begin cases l₂, refl, simp [merge],
end
example {α : Type} (l₂ : list α) : l₂ = append list.nil l₂ := begin refl end
```

1: is there something wrong with the way I've defined merge? the reduce command times out, although `#eval`

works

2: I had the mental model that definitions would be normalized away inside proofs, so I was expecting `refl`

to prove the first `example`

. is there a way for me to see why it works for `append`

but `simp`

is required for `merge`

? why does that proof require an initial case split?

#### Yakov Pechersky (Dec 28 2020 at 19:07):

For me, in an empty file with your first defn, `#reduce`

does not time out for me.

#### Scott Kovach (Dec 28 2020 at 19:22):

oops, I agree. it seems that adding `import data.list.perm`

causes the timeout (I haven't intentionally used anything from this module, but I was planning to)

#### Kevin Buzzard (Dec 28 2020 at 19:22):

`#print prefix merge`

shows you what is really going on. The four equations e.g. `merge.equations._eqn_3`

show you the things which are true, but Lean will not guarantee that they're true by definition.

#### Mario Carneiro (Dec 28 2020 at 19:23):

It's not possible for all three equations in `merge`

to be defeqs

#### Mario Carneiro (Dec 28 2020 at 19:24):

because you have to case on one of the arguments first; if you case on `xs`

then `merge xs [] = xs`

will not be defeq

#### Mario Carneiro (Dec 28 2020 at 19:25):

incidentally, lean has a slightly stupid case tree generator so it manages to break *both* of the first two defeqs

#### Kevin Buzzard (Dec 28 2020 at 19:25):

But there is another issue here:

```
def merge {α : Type} [linear_order α] : list α → list α → list α
| [] [] := []
| [] (y::ys) := y::ys
| (x::xs) [] := x::xs
| (x::xs) (y::ys) := if x ≤ y then x :: merge xs (y::ys) else y :: merge (x::xs) ys
```

does not make `example {α : Type} [linear_order α] (x : α) (xs : list α) : merge (x :: xs) [] = x :: xs := rfl`

work.

#### Mario Carneiro (Dec 28 2020 at 19:26):

oh, right, this function also has a weird recursion structure

#### Mario Carneiro (Dec 28 2020 at 19:27):

it's probably being compiled with well founded recursion which breaks all the defeqs

#### Kevin Buzzard (Dec 28 2020 at 19:27):

`example {α : Type} [linear_order α] : merge ([] : list α) [] = [] := rfl`

works!

#### Mario Carneiro (Dec 28 2020 at 19:27):

It's possible to compile this one to satisfy the four equations you wrote

#### Mario Carneiro (Dec 28 2020 at 19:31):

```
def merge {α : Type} [linear_order α] : list α → list α → list α :=
λ xs, list.rec_on xs (λ ys, ys) $ λ x xs IH ys,
list.rec_on ys (x::xs) $ λ y ys ih,
if x ≤ y then x :: IH (y::ys) else y :: ih
variables {α : Type} [linear_order α] (x y : α) (xs ys : list α)
example : merge [] ys = ys := rfl
example : merge (x::xs) [] = x::xs := rfl
example : merge (x::xs) (y::ys) =
if x ≤ y then x :: merge xs (y::ys) else y :: merge (x::xs) ys := rfl
```

#### Mario Carneiro (Dec 28 2020 at 19:32):

but

```
example : merge xs [] = xs := rfl -- fails
```

#### Kevin Buzzard (Dec 28 2020 at 19:34):

This is about the best one can expect, I guess.

#### Mario Carneiro (Dec 28 2020 at 19:34):

right, the different cases that you get defeqs for have to be disjoint

#### Kevin Buzzard (Dec 28 2020 at 19:36):

People like me who take definitional equality less seriously just need to know the trick that `simp [merge]`

will solve these lemmas. In a typical Lean formalisation one would in fact take these four "definitional" lemmas and restate them (with any notation which one wants to use), prove them (with `rfl`

or not depending on what works) and then tag the lemmas with `simp`

and let the simplifier do the rewriting for you.

#### Scott Kovach (Dec 28 2020 at 19:47):

thanks Kevin and Mario! i'll carry on with propositional equalities for now

Last updated: Dec 20 2023 at 11:08 UTC