liveBook · Manning

View

As explained in Type-Driven Development with Idris

An alternative representation of a value that exposes its structure for pattern matching without requiring access to the value’s original constructors.

A view gives another way to inspect a value. In Idris, it is a dependent type indexed by the value being inspected. Matching a view’s constructors reveals facts about the original value, providing patterns beyond those offered by its ordinary constructors. section 10.0 section 10.1.1

For example, a list normally matches as empty or as a head and tail. Matching directly on xs ++ [x] fails: ++ is a function, and Idris cannot generally recover its inputs from its result. A view can instead describe an empty list or a list with an initial portion and a last element. section 10.1 section 10.1.1

data ListLast : List a -> Type where
     Empty : ListLast []                                              #1
     NonEmpty : (xs : List a) -> (x : a) -> ListLast (xs ++ [x])      #2

ListLast indexes each constructor by the list it describes. Matching NonEmpty xs x establishes that the original list has the form xs ++ [x]. section 10.1.1

A covering function constructs a view for an input: listLast has type (xs : List a) -> ListLast xs. Once it produces a view, a helper can match on both the input and the view. The with construct expresses this dependent match without a separate helper. section 10.1.2 section 10.1.3

describeListEnd : List Int -> String
describeListEnd input with (listLast input)
  describeListEnd [] | Empty = "Empty"
  describeListEnd (xs ++ [x]) | (NonEmpty xs x)
          = "Non-empty, initial portion = " ++ show xs

The with block computes listLast input, then splits on the resulting view. Each view pattern refines the corresponding input pattern. section 10.1.3

Views also guide traversals. A direct reverse can repeatedly find the last element, but rebuilding its view on every recursive call is inefficient, and Idris cannot establish totality. A recursive view instead carries the view of the remaining input; passing it directly to the recursive with block avoids rebuilding it. section 10.1.4 section 10.2.2

myReverse : List a -> List a
myReverse input with (snocList input)
  myReverse [] | Empty = []
  myReverse (xs ++ [x]) | (Snoc rec) = x :: myReverse xs | rec

Here rec is the recursive view. The call myReverse xs | rec reuses it; this implementation runs in linear time and Idris checks it as total. section 10.2.2

Splitting a list for merge sort

A split view supplies empty, singleton, and concatenated-list cases. The recursive SplitRec view provides views of both halves, allowing merge sort to recurse through those views and be checked as total. SplitRec is available in Data.List.Views. section 10.1.5 section 10.2.4

Inspecting an abstract store

A store can export operations for creating and adding entries while hiding its representation. StoreView exposes empty and added-entry cases, so clients can traverse or filter entries without knowing the underlying data structure. section 10.3.2 section 10.3.3

How Type-Driven Development with Idris covers it

How deep it goes
Develops dependent view types, covering functions, with blocks, recursive traversal, efficiency, and totality checking through implementations.
Examples
Works through list-end matching, reversal, merge sort, and traversal and filtering of a data store.
What you can do after
Build views from scratch and apply Idris library views to traversals, including total list reversal and merge sort.
How it connects
Connects dependent types and pattern matching with recursion, termination checking, and data abstraction.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Type-Driven Development with Idris. The section links point to the parts of the book it draws on.