# Functional Programming

## A Heap

### A New Heap

A **heap** is a tree structure where the largest element is in the root of the tree and where the left and right branch are heaps. Define a data structure that is suitable to represent a heap and implement a function `new/0` that returns a heap. Assume that we only should handle integers.

```elixir
@spec new() :: heap()
```

### Insert

Implement the function `add/2` that adds an integer to a heap.

```elixir
@spec add(heap(), integer()) :: heap()
```

To keep the heap balanced you should switch the left and right branches that is, when you add an element to a branch you add it to the right branch but make the result the left branch of the heap.

### Pop

Implement the function `pop/1` that removes the highest element in an heap and returns either `:fail`, if the heap is empty or `{:ok, integer(), heap()}`

```elixir
@spec pop(heap()) :fail | {:ok, integer(), heap()}
```

### Swap

Implement the function `swap/2` that takes a heap and a number and returns `{:ok, integer(), heap()}` where the number is the highest number and the heap the remaining heap. The function should have the same meaning as first `add/2` a number to a heap and then `pop/1` the highest but we should do this in one function, not by calling the two functions.

```elixir
@spec swap(heap(), integer()) {:ok, integer(), heap()}
```

### A General Heap

The heap we now have will have the largest element in the root and be limited to integers (or what is comparable with `<`). Implement a function `add/3` that takes a heap, an element and a function that can be used to compare two elements. The function `add/3` should as before add an element to a heap but now used the provided function when doing the comparison.

```elixir
@type cmp() :: (any(), any() > bool())
@spec add(heap(), any(), cmp()) :: heap()
```

Specify a type `cheap()` that holds a function for comparison and a heap. Implement a function `new/1` that takes a function and returns a structure of the type `cheap()`.

```elixir
@spec new(cmp()) :: cheap()
```

Implement a function `add/2` that takes a structure of type `cheap()`, that calls `add/3` with the correct arguments and returns a structure of the same form.

```elixir
@spec add(cheap(), any()) :: cheap()
```

## Mirror a Tree

If we have the below definition of a function that mirrors a tree, what is the asymptotic time complexity of the function?

```elixir
def mirror(nil) do nil end

def mirror({:node, left, right}) do
  {:node, mirror(right), mirror(left)}
end
```

## Complexity of a Queue

Assume that we represent a queue with the help of two lists and have the below implementation of `enqueue/2` and `dequeue/1`. What is the amortised time complexity for **adding and then removing an element from a queue**?

```elixir
def enqueue({:queue, head, tail}, elem) do
  {:queue, head, [elem|tail]}
end

def dequeue({:queue, [], []}) do :fail end

def dequeue({:queue, [elem|head], tail}) do
  {:ok, elem, {:queue, head, tail}
end

def dequeue({:queue, [], tail}) do
  dequeue({:queue, reverse(tail), []})
end
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://id1019.gitbook.io/exercises/problems/functional.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.