| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Dhall.Core
Description
This module contains the core calculus for the Dhall language.
Dhall is essentially a fork of the morte compiler but with more built-in
functionality, better error messages, and Haskell integration
Synopsis
- data Const
- newtype Directory = Directory {
- components :: [Text]
- data File = File {}
- data FilePrefix
- data Import = Import {}
- data ImportHashed = ImportHashed {
- hash :: Maybe (Digest SHA256)
- importType :: ImportType
- data ImportMode
- data ImportType
- data URL = URL {}
- type Path = Import
- data Scheme
- data Var = V Text !Integer
- data Binding s a = Binding {}
- data Chunks s a = Chunks [(Text, Expr s a)] Text
- data Expr s a
- = Const Const
- | Var Var
- | Lam Text (Expr s a) (Expr s a)
- | Pi Text (Expr s a) (Expr s a)
- | App (Expr s a) (Expr s a)
- | Let (NonEmpty (Binding s a)) (Expr s a)
- | Annot (Expr s a) (Expr s a)
- | Bool
- | BoolLit Bool
- | BoolAnd (Expr s a) (Expr s a)
- | BoolOr (Expr s a) (Expr s a)
- | BoolEQ (Expr s a) (Expr s a)
- | BoolNE (Expr s a) (Expr s a)
- | BoolIf (Expr s a) (Expr s a) (Expr s a)
- | Natural
- | NaturalLit Natural
- | NaturalFold
- | NaturalBuild
- | NaturalIsZero
- | NaturalEven
- | NaturalOdd
- | NaturalToInteger
- | NaturalShow
- | NaturalPlus (Expr s a) (Expr s a)
- | NaturalTimes (Expr s a) (Expr s a)
- | Integer
- | IntegerLit Integer
- | IntegerShow
- | IntegerToDouble
- | Double
- | DoubleLit Double
- | DoubleShow
- | Text
- | TextLit (Chunks s a)
- | TextAppend (Expr s a) (Expr s a)
- | List
- | ListLit (Maybe (Expr s a)) (Seq (Expr s a))
- | ListAppend (Expr s a) (Expr s a)
- | ListBuild
- | ListFold
- | ListLength
- | ListHead
- | ListLast
- | ListIndexed
- | ListReverse
- | Optional
- | OptionalLit (Expr s a) (Maybe (Expr s a))
- | Some (Expr s a)
- | None
- | OptionalFold
- | OptionalBuild
- | Record (Map Text (Expr s a))
- | RecordLit (Map Text (Expr s a))
- | Union (Map Text (Expr s a))
- | UnionLit Text (Expr s a) (Map Text (Expr s a))
- | Combine (Expr s a) (Expr s a)
- | CombineTypes (Expr s a) (Expr s a)
- | Prefer (Expr s a) (Expr s a)
- | Merge (Expr s a) (Expr s a) (Maybe (Expr s a))
- | Constructors (Expr s a)
- | Field (Expr s a) Text
- | Project (Expr s a) (Set Text)
- | Note s (Expr s a)
- | ImportAlt (Expr s a) (Expr s a)
- | Embed a
- alphaNormalize :: Expr s a -> Expr s a
- normalize :: Eq a => Expr s a -> Expr t a
- normalizeWith :: Eq a => Normalizer a -> Expr s a -> Expr t a
- normalizeWithM :: (Eq a, Monad m) => NormalizerM m a -> Expr s a -> m (Expr t a)
- type Normalizer a = NormalizerM Identity a
- type NormalizerM m a = forall s. Expr s a -> m (Maybe (Expr s a))
- data ReifiedNormalizer a = ReifiedNormalizer {}
- judgmentallyEqual :: Eq a => Expr s a -> Expr t a -> Bool
- subst :: Var -> Expr s a -> Expr s a -> Expr s a
- shift :: Integer -> Var -> Expr s a -> Expr s a
- isNormalized :: Eq a => Expr s a -> Bool
- isNormalizedWith :: (Eq s, Eq a) => Normalizer a -> Expr s a -> Bool
- denote :: Expr s a -> Expr t a
- freeIn :: Eq a => Var -> Expr s a -> Bool
- pretty :: Pretty a => a -> Text
- internalError :: Text -> forall b. b
- reservedIdentifiers :: HashSet Text
- escapeText :: Text -> Text
- subExpressions :: Applicative f => (Expr s a -> f (Expr s a)) -> Expr s a -> f (Expr s a)
- pathCharacter :: Char -> Bool
Syntax
Constants for a pure type system
The axioms are:
⊦ Type : Kind ⊦ Kind : Sort
... and the valid rule pairs are:
⊦ Type ↝ Type : Type -- Functions from terms to terms (ordinary functions) ⊦ Kind ↝ Type : Type -- Functions from types to terms (type-polymorphic functions) ⊦ Sort ↝ Type : Type -- Functions from kinds to terms ⊦ Kind ↝ Kind : Kind -- Functions from types to types (type-level functions) ⊦ Sort ↝ Kind : Sort -- Functions from kinds to types (kind-polymorphic functions) ⊦ Sort ↝ Sort : Sort -- Functions from kinds to kinds (kind-level functions)
Note that Dhall does not support functions from terms to types and therefore Dhall is not a dependently typed language
Instances
| Bounded Const # | |
| Enum Const # | |
| Eq Const # | |
| Data Const # | |
Defined in Dhall.Core Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Const -> c Const # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Const # dataTypeOf :: Const -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Const) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Const) # gmapT :: (forall b. Data b => b -> b) -> Const -> Const # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Const -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Const -> r # gmapQ :: (forall d. Data d => d -> u) -> Const -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Const -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Const -> m Const # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Const -> m Const # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Const -> m Const # | |
| Show Const # | |
| Generic Const # | |
| Pretty Const # | |
Defined in Dhall.Core | |
| type Rep Const # | |
Internal representation of a directory that stores the path components in reverse order
In other words, the directory /foo/bar/baz is encoded as
Directory { components = [ "baz", "bar", "foo" ] }
Constructors
| Directory | |
Fields
| |
Instances
| Eq Directory # | |
| Ord Directory # | |
| Show Directory # | |
| Generic Directory # | |
| Semigroup Directory # | |
| Pretty Directory # | |
Defined in Dhall.Core | |
| type Rep Directory # | |
Defined in Dhall.Core | |
Instances
| Eq File # | |
| Ord File # | |
| Show File # | |
| Generic File # | |
| Semigroup File # | |
| Pretty File # | |
Defined in Dhall.Core | |
| type Rep File # | |
Defined in Dhall.Core type Rep File = D1 (MetaData "File" "Dhall.Core" "dhall-1.19.1-Ah0vXR4FE0YHUH3zyrPtLe" False) (C1 (MetaCons "File" PrefixI True) (S1 (MetaSel (Just "directory") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Directory) :*: S1 (MetaSel (Just "file") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Text))) | |
data FilePrefix #
The beginning of a file path which anchors subsequent path components
Instances
| Eq FilePrefix # | |
Defined in Dhall.Core | |
| Ord FilePrefix # | |
Defined in Dhall.Core Methods compare :: FilePrefix -> FilePrefix -> Ordering # (<) :: FilePrefix -> FilePrefix -> Bool # (<=) :: FilePrefix -> FilePrefix -> Bool # (>) :: FilePrefix -> FilePrefix -> Bool # (>=) :: FilePrefix -> FilePrefix -> Bool # max :: FilePrefix -> FilePrefix -> FilePrefix # min :: FilePrefix -> FilePrefix -> FilePrefix # | |
| Show FilePrefix # | |
Defined in Dhall.Core Methods showsPrec :: Int -> FilePrefix -> ShowS # show :: FilePrefix -> String # showList :: [FilePrefix] -> ShowS # | |
| Generic FilePrefix # | |
Defined in Dhall.Core Associated Types type Rep FilePrefix :: Type -> Type # | |
| Pretty FilePrefix # | |
Defined in Dhall.Core | |
| type Rep FilePrefix # | |
Defined in Dhall.Core | |
Reference to an external resource
Constructors
| Import | |
Fields | |
Instances
| Eq Import # | |
| Ord Import # | |
| Show Import # | |
| Generic Import # | |
| Semigroup Import # | |
| Pretty Import # | |
Defined in Dhall.Core | |
| type Rep Import # | |
Defined in Dhall.Core type Rep Import = D1 (MetaData "Import" "Dhall.Core" "dhall-1.19.1-Ah0vXR4FE0YHUH3zyrPtLe" False) (C1 (MetaCons "Import" PrefixI True) (S1 (MetaSel (Just "importHashed") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 ImportHashed) :*: S1 (MetaSel (Just "importMode") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 ImportMode))) | |
data ImportHashed #
A ImportType extended with an optional hash for semantic integrity checks
Constructors
| ImportHashed | |
Fields
| |
Instances
data ImportMode #
How to interpret the import's contents (i.e. as Dhall code or raw text)
Instances
| Eq ImportMode # | |
Defined in Dhall.Core | |
| Ord ImportMode # | |
Defined in Dhall.Core Methods compare :: ImportMode -> ImportMode -> Ordering # (<) :: ImportMode -> ImportMode -> Bool # (<=) :: ImportMode -> ImportMode -> Bool # (>) :: ImportMode -> ImportMode -> Bool # (>=) :: ImportMode -> ImportMode -> Bool # max :: ImportMode -> ImportMode -> ImportMode # min :: ImportMode -> ImportMode -> ImportMode # | |
| Show ImportMode # | |
Defined in Dhall.Core Methods showsPrec :: Int -> ImportMode -> ShowS # show :: ImportMode -> String # showList :: [ImportMode] -> ShowS # | |
| Generic ImportMode # | |
Defined in Dhall.Core Associated Types type Rep ImportMode :: Type -> Type # | |
| type Rep ImportMode # | |
data ImportType #
The type of import (i.e. local vs. remote vs. environment)
Constructors
| Local FilePrefix File | Local path |
| Remote URL | URL of remote resource and optional headers stored in an import |
| Env Text | Environment variable |
| Missing |
Instances
Constructors
| URL | |
Instances
| Eq URL # | |
| Ord URL # | |
| Show URL # | |
| Generic URL # | |
| type Rep URL # | |
Defined in Dhall.Core type Rep URL = D1 (MetaData "URL" "Dhall.Core" "dhall-1.19.1-Ah0vXR4FE0YHUH3zyrPtLe" False) (C1 (MetaCons "URL" PrefixI True) ((S1 (MetaSel (Just "scheme") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Scheme) :*: (S1 (MetaSel (Just "authority") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Text) :*: S1 (MetaSel (Just "path") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 File))) :*: (S1 (MetaSel (Just "query") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Maybe Text)) :*: (S1 (MetaSel (Just "fragment") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Maybe Text)) :*: S1 (MetaSel (Just "headers") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Maybe ImportHashed)))))) | |
Deprecated: Use Dhall.Core.Import instead
Type synonym for Import, provided for backwards compatibility
Label for a bound variable
The Expr field is the variable's name (i.e. "x").
The Int field disambiguates variables with the same name if there are
multiple bound variables of the same name in scope. Zero refers to the
nearest bound variable and the index increases by one for each bound
variable of the same name going outward. The following diagram may help:
┌──refers to──┐
│ │
v │
λ(x : Type) → λ(y : Type) → λ(x : Type) → x@0
┌─────────────────refers to─────────────────┐
│ │
v │
λ(x : Type) → λ(y : Type) → λ(x : Type) → x@1This Int behaves like a De Bruijn index in the special case where all
variables have the same name.
You can optionally omit the index if it is 0:
┌─refers to─┐
│ │
v │
λ(x : Type) → λ(y : Type) → λ(x : Type) → xZero indices are omitted when pretty-printing Vars and non-zero indices
appear as a numeric suffix.
Instances
| Eq Var # | |
| Data Var # | |
Defined in Dhall.Core Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Var -> c Var # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Var # dataTypeOf :: Var -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Var) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Var) # gmapT :: (forall b. Data b => b -> b) -> Var -> Var # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Var -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Var -> r # gmapQ :: (forall d. Data d => d -> u) -> Var -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Var -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Var -> m Var # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Var -> m Var # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Var -> m Var # | |
| Show Var # | |
| IsString Var # | |
Defined in Dhall.Core Methods fromString :: String -> Var # | |
| Generic Var # | |
| Pretty Var # | |
Defined in Dhall.Core | |
| type Rep Var # | |
Defined in Dhall.Core type Rep Var = D1 (MetaData "Var" "Dhall.Core" "dhall-1.19.1-Ah0vXR4FE0YHUH3zyrPtLe" False) (C1 (MetaCons "V" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Text) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Integer))) | |
Instances
| Bifunctor Binding # | |
| Functor (Binding s) # | |
| Foldable (Binding s) # | |
Defined in Dhall.Core Methods fold :: Monoid m => Binding s m -> m # foldMap :: Monoid m => (a -> m) -> Binding s a -> m # foldr :: (a -> b -> b) -> b -> Binding s a -> b # foldr' :: (a -> b -> b) -> b -> Binding s a -> b # foldl :: (b -> a -> b) -> b -> Binding s a -> b # foldl' :: (b -> a -> b) -> b -> Binding s a -> b # foldr1 :: (a -> a -> a) -> Binding s a -> a # foldl1 :: (a -> a -> a) -> Binding s a -> a # toList :: Binding s a -> [a] # length :: Binding s a -> Int # elem :: Eq a => a -> Binding s a -> Bool # maximum :: Ord a => Binding s a -> a # minimum :: Ord a => Binding s a -> a # | |
| Traversable (Binding s) # | |
| (Eq s, Eq a) => Eq (Binding s a) # | |
| (Data s, Data a) => Data (Binding s a) # | |
Defined in Dhall.Core Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Binding s a -> c (Binding s a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Binding s a) # toConstr :: Binding s a -> Constr # dataTypeOf :: Binding s a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Binding s a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Binding s a)) # gmapT :: (forall b. Data b => b -> b) -> Binding s a -> Binding s a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Binding s a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Binding s a -> r # gmapQ :: (forall d. Data d => d -> u) -> Binding s a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Binding s a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Binding s a -> m (Binding s a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Binding s a -> m (Binding s a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Binding s a -> m (Binding s a) # | |
| (Show s, Show a) => Show (Binding s a) # | |
| Generic (Binding s a) # | |
| type Rep (Binding s a) # | |
Defined in Dhall.Core type Rep (Binding s a) = D1 (MetaData "Binding" "Dhall.Core" "dhall-1.19.1-Ah0vXR4FE0YHUH3zyrPtLe" False) (C1 (MetaCons "Binding" PrefixI True) (S1 (MetaSel (Just "variable") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Text) :*: (S1 (MetaSel (Just "annotation") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Maybe (Expr s a))) :*: S1 (MetaSel (Just "value") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Expr s a))))) | |
The body of an interpolated Text literal
Instances
| Functor (Chunks s) # | |
| Foldable (Chunks s) # | |
Defined in Dhall.Core Methods fold :: Monoid m => Chunks s m -> m # foldMap :: Monoid m => (a -> m) -> Chunks s a -> m # foldr :: (a -> b -> b) -> b -> Chunks s a -> b # foldr' :: (a -> b -> b) -> b -> Chunks s a -> b # foldl :: (b -> a -> b) -> b -> Chunks s a -> b # foldl' :: (b -> a -> b) -> b -> Chunks s a -> b # foldr1 :: (a -> a -> a) -> Chunks s a -> a # foldl1 :: (a -> a -> a) -> Chunks s a -> a # elem :: Eq a => a -> Chunks s a -> Bool # maximum :: Ord a => Chunks s a -> a # minimum :: Ord a => Chunks s a -> a # | |
| Traversable (Chunks s) # | |
| (Eq s, Eq a) => Eq (Chunks s a) # | |
| (Data s, Data a) => Data (Chunks s a) # | |
Defined in Dhall.Core Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Chunks s a -> c (Chunks s a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Chunks s a) # toConstr :: Chunks s a -> Constr # dataTypeOf :: Chunks s a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Chunks s a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Chunks s a)) # gmapT :: (forall b. Data b => b -> b) -> Chunks s a -> Chunks s a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Chunks s a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Chunks s a -> r # gmapQ :: (forall d. Data d => d -> u) -> Chunks s a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Chunks s a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Chunks s a -> m (Chunks s a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Chunks s a -> m (Chunks s a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Chunks s a -> m (Chunks s a) # | |
| (Show s, Show a) => Show (Chunks s a) # | |
| IsString (Chunks s a) # | |
Defined in Dhall.Core Methods fromString :: String -> Chunks s a # | |
| Generic (Chunks s a) # | |
| Semigroup (Chunks s a) # | |
| Monoid (Chunks s a) # | |
| type Rep (Chunks s a) # | |
Defined in Dhall.Core type Rep (Chunks s a) = D1 (MetaData "Chunks" "Dhall.Core" "dhall-1.19.1-Ah0vXR4FE0YHUH3zyrPtLe" False) (C1 (MetaCons "Chunks" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 [(Text, Expr s a)]) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Text))) | |
Syntax tree for expressions
Constructors
| Const Const | Const c ~ c |
| Var Var | Var (V x 0) ~ x Var (V x n) ~ x@n |
| Lam Text (Expr s a) (Expr s a) | Lam x A b ~ λ(x : A) -> b |
| Pi Text (Expr s a) (Expr s a) | Pi "_" A B ~ A -> B Pi x A B ~ ∀(x : A) -> B |
| App (Expr s a) (Expr s a) | App f a ~ f a |
| Let (NonEmpty (Binding s a)) (Expr s a) | Let [Binding x Nothing r] e ~ let x = r in e Let [Binding x (Just t) r] e ~ let x : t = r in e |
| Annot (Expr s a) (Expr s a) | Annot x t ~ x : t |
| Bool | Bool ~ Bool |
| BoolLit Bool | BoolLit b ~ b |
| BoolAnd (Expr s a) (Expr s a) | BoolAnd x y ~ x && y |
| BoolOr (Expr s a) (Expr s a) | BoolOr x y ~ x || y |
| BoolEQ (Expr s a) (Expr s a) | BoolEQ x y ~ x == y |
| BoolNE (Expr s a) (Expr s a) | BoolNE x y ~ x != y |
| BoolIf (Expr s a) (Expr s a) (Expr s a) | BoolIf x y z ~ if x then y else z |
| Natural | Natural ~ Natural |
| NaturalLit Natural | NaturalLit n ~ n |
| NaturalFold | NaturalFold ~ Natural/fold |
| NaturalBuild | NaturalBuild ~ Natural/build |
| NaturalIsZero | NaturalIsZero ~ Natural/isZero |
| NaturalEven | NaturalEven ~ Natural/even |
| NaturalOdd | NaturalOdd ~ Natural/odd |
| NaturalToInteger | NaturalToInteger ~ Natural/toInteger |
| NaturalShow | NaturalShow ~ Natural/show |
| NaturalPlus (Expr s a) (Expr s a) | NaturalPlus x y ~ x + y |
| NaturalTimes (Expr s a) (Expr s a) | NaturalTimes x y ~ x * y |
| Integer | Integer ~ Integer |
| IntegerLit Integer | IntegerLit n ~ ±n |
| IntegerShow | IntegerShow ~ Integer/show |
| IntegerToDouble | IntegerToDouble ~ Integer/toDouble |
| Double | Double ~ Double |
| DoubleLit Double | DoubleLit n ~ n |
| DoubleShow | DoubleShow ~ Double/show |
| Text | Text ~ Text |
| TextLit (Chunks s a) | TextLit (Chunks [(t1, e1), (t2, e2)] t3) ~ "t1${e1}t2${e2}t3" |
| TextAppend (Expr s a) (Expr s a) | TextAppend x y ~ x ++ y |
| List | List ~ List |
| ListLit (Maybe (Expr s a)) (Seq (Expr s a)) | ListLit (Just t ) [x, y, z] ~ [x, y, z] : List t ListLit Nothing [x, y, z] ~ [x, y, z] |
| ListAppend (Expr s a) (Expr s a) | ListAppend x y ~ x # y |
| ListBuild | ListBuild ~ List/build |
| ListFold | ListFold ~ List/fold |
| ListLength | ListLength ~ List/length |
| ListHead | ListHead ~ List/head |
| ListLast | ListLast ~ List/last |
| ListIndexed | ListIndexed ~ List/indexed |
| ListReverse | ListReverse ~ List/reverse |
| Optional | Optional ~ Optional |
| OptionalLit (Expr s a) (Maybe (Expr s a)) | OptionalLit t (Just e) ~ [e] : Optional t OptionalLit t Nothing ~ [] : Optional t |
| Some (Expr s a) | Some e ~ Some e |
| None | None ~ None |
| OptionalFold | OptionalFold ~ Optional/fold |
| OptionalBuild | OptionalBuild ~ Optional/build |
| Record (Map Text (Expr s a)) | Record [(k1, t1), (k2, t2)] ~ { k1 : t1, k2 : t1 } |
| RecordLit (Map Text (Expr s a)) | RecordLit [(k1, v1), (k2, v2)] ~ { k1 = v1, k2 = v2 } |
| Union (Map Text (Expr s a)) | Union [(k1, t1), (k2, t2)] ~ < k1 : t1 | k2 : t2 > |
| UnionLit Text (Expr s a) (Map Text (Expr s a)) | UnionLit k v [(k1, t1), (k2, t2)] ~ < k = v | k1 : t1 | k2 : t2 > |
| Combine (Expr s a) (Expr s a) | Combine x y ~ x ∧ y |
| CombineTypes (Expr s a) (Expr s a) | CombineTypes x y ~ x ⩓ y |
| Prefer (Expr s a) (Expr s a) | Prefer x y ~ x ⫽ y |
| Merge (Expr s a) (Expr s a) (Maybe (Expr s a)) | Merge x y (Just t ) ~ merge x y : t Merge x y Nothing ~ merge x y |
| Constructors (Expr s a) | Constructors e ~ constructors e |
| Field (Expr s a) Text | Field e x ~ e.x |
| Project (Expr s a) (Set Text) | Project e xs ~ e.{ xs } |
| Note s (Expr s a) | Note s x ~ e |
| ImportAlt (Expr s a) (Expr s a) | ImportAlt ~ e1 ? e2 |
| Embed a | Embed import ~ import |
Instances
Normalization
alphaNormalize :: Expr s a -> Expr s a #
α-normalize an expression by renaming all bound variables to "_" and
using De Bruijn indices to distinguish them
>>>alphaNormalize (Lam "a" (Const Type) (Lam "b" (Const Type) (Lam "x" "a" (Lam "y" "b" "x"))))Lam "_" (Const Type) (Lam "_" (Const Type) (Lam "_" (Var (V "_" 1)) (Lam "_" (Var (V "_" 1)) (Var (V "_" 1)))))
α-normalization does not affect free variables:
>>>alphaNormalize "x"Var (V "x" 0)
normalize :: Eq a => Expr s a -> Expr t a #
Reduce an expression to its normal form, performing beta reduction
normalize does not type-check the expression. You may want to type-check
expressions before normalizing them since normalization can convert an
ill-typed expression into a well-typed expression.
However, normalize will not fail if the expression is ill-typed and will
leave ill-typed sub-expressions unevaluated.
normalizeWith :: Eq a => Normalizer a -> Expr s a -> Expr t a #
Reduce an expression to its normal form, performing beta reduction and applying any custom definitions.
normalizeWith is designed to be used with function typeWith. The typeWith
function allows typing of Dhall functions in a custom typing context whereas
normalizeWith allows evaluating Dhall expressions in a custom context.
To be more precise normalizeWith applies the given normalizer when it finds an
application term that it cannot reduce by other means.
Note that the context used in normalization will determine the properties of normalization. That is, if the functions in custom context are not total then the Dhall language, evaluated with those functions is not total either.
normalizeWithM :: (Eq a, Monad m) => NormalizerM m a -> Expr s a -> m (Expr t a) #
type Normalizer a = NormalizerM Identity a #
type NormalizerM m a = forall s. Expr s a -> m (Maybe (Expr s a)) #
Use this to wrap you embedded functions (see normalizeWith) to make them
polymorphic enough to be used.
data ReifiedNormalizer a #
A reified Normalizer, which can be stored in structures without
running into impredicative polymorphism.
Constructors
| ReifiedNormalizer | |
Fields | |
subst :: Var -> Expr s a -> Expr s a -> Expr s a #
Substitute all occurrences of a variable with an expression
subst x C B ~ B[x := C]
shift :: Integer -> Var -> Expr s a -> Expr s a #
shift is used by both normalization and type-checking to avoid variable
capture by shifting variable indices
For example, suppose that you were to normalize the following expression:
λ(a : Type) → λ(x : a) → (λ(y : a) → λ(x : a) → y) x
If you were to substitute y with x without shifting any variable
indices, then you would get the following incorrect result:
λ(a : Type) → λ(x : a) → λ(x : a) → x -- Incorrect normalized form
In order to substitute x in place of y we need to shift x by 1 in
order to avoid being misinterpreted as the x bound by the innermost
lambda. If we perform that shift then we get the correct result:
λ(a : Type) → λ(x : a) → λ(x : a) → x@1
As a more worked example, suppose that you were to normalize the following expression:
λ(a : Type) → λ(f : a → a → a) → λ(x : a) → λ(x : a) → (λ(x : a) → f x x@1) x@1
The correct normalized result would be:
λ(a : Type) → λ(f : a → a → a) → λ(x : a) → λ(x : a) → f x@1 x
The above example illustrates how we need to both increase and decrease variable indices as part of substitution:
- We need to increase the index of the outer
x@1tox@2before we substitute it into the body of the innermost lambda expression in order to avoid variable capture. This substitution changes the body of the lambda expression to(f x@2 x@1) - We then remove the innermost lambda and therefore decrease the indices of
both
xs in(f x@2 x@1)to(f x@1 x)in order to reflect that one lessxvariable is now bound within that scope
Formally, (shift d (V x n) e) modifies the expression e by adding d to
the indices of all variables named x whose indices are greater than
(n + m), where m is the number of bound variables of the same name
within that scope
In practice, d is always 1 or -1 because we either:
- increment variables by
1to avoid variable capture during substitution - decrement variables by
1when deleting lambdas after substitution
n starts off at 0 when substitution begins and increments every time we
descend into a lambda or let expression that binds a variable of the same
name in order to avoid shifting the bound variables by mistake.
isNormalized :: Eq a => Expr s a -> Bool #
Quickly check if an expression is in normal form
isNormalizedWith :: (Eq s, Eq a) => Normalizer a -> Expr s a -> Bool #
Check if an expression is in a normal form given a context of evaluation.
Unlike isNormalized, this will fully normalize and traverse through the expression.
It is much more efficient to use isNormalized.
freeIn :: Eq a => Var -> Expr s a -> Bool #
Detect if the given variable is free within the given expression
>>>"x" `freeIn` "x"True>>>"x" `freeIn` "y"False>>>"x" `freeIn` Lam "x" (Const Type) "x"False
Pretty-printing
Miscellaneous
internalError :: Text -> forall b. b #
Utility function used to throw internal errors that should never happen (in theory) but that are not enforced by the type system
reservedIdentifiers :: HashSet Text #
The set of reserved identifiers for the Dhall language
escapeText :: Text -> Text #
subExpressions :: Applicative f => (Expr s a -> f (Expr s a)) -> Expr s a -> f (Expr s a) #
A traversal over the immediate sub-expressions of an expression.
pathCharacter :: Char -> Bool #
Returns True if the given Char is valid within an unquoted path
component
This is exported for reuse within the Dhall.Parser.Token module