-
Notifications
You must be signed in to change notification settings - Fork 6
Semantics
This page documents the semantics of some non-obvious functions, as well as general conventions.
The argument order of Husk functions is chosen in a way that (hopefully) makes partial application as convenient as possible, which is sometimes in conflict with the "natural" order.
For example, the function minus
(-
) takes two numbers, k
and n
in this order, and returns n - k
.
This is because the function that subtracts k
from its argument is more useful than the function that subtracts its argument from n
.
In the source code, the partial application -3
also visually hints that 3
is subtracted from something.
Other functions that take their arguments in a non-obvious order include /÷%‰
(division and modulus), &|
(short-circuiting Boolean operators) and ≥≤><
(comparison).
Some functions can take their arguments in either order, since the correct semantics can be inferred from their types.
These include !
(indexing into lists), €£
(finding indices in lists), ↑↓
(prefixes and suffixes of lists) and RṘ
(repeating values).
If a function takes another function as an argument, it is generally the first argument.
In Husk, a value whose type belongs to the Concrete
typeclass (numbers and characters, and pairs and lists thereof) has a property called truthiness: it can be either truthy or falsy.
Some functions, like if
and filter
, can inspect the truthiness of a value.
The truthiness of a concrete value is determined as follows:
- A number is falsy if it is equal to
0
(which includes the floating point value0.0
and the special valueAny
), and truthy otherwise. - Whitespace characters are falsy, others are truthy. This is determined by the Haskell function
Data.Char.isSpace
. - An empty list is falsy, other lists are truthy.
- A pair is falsy if either component is falsy.
Some functions are designed to determine whether a condition holds, like eq
and all
, so they return a concrete value whose truthiness encodes the condition.
By convention, such functions return nonnegative integers.
Some only return 0
for falsy and 1
for truthy, but others pack additional information about the condition into the return value.
Here are the semantics of some predicates.
-
eq
,congr
,simil
,small
and variants (=≡≈ε
) always return0
or1
. -
divids
(¦
) returnsb/a
ifa
dividesb
, and0
otherwise. -
neq
(≠
) returns0
for equal values, and a "measure of inequality" for distinct values. This is ceiling of absolute difference for numbers, absolute difference of codepoints for characters, and index of first differing element for lists. On a pair,neq
recurses to the first coordinates and then the second ones, returning the first nonzero result, if any. -
ge
,le
,gt
andlt
(≥≤><
) behave similarly toneq
, except they return0
for one ordering, andge
andle
have their values incremented by one in the truthy cases. -
all
,same
andsameon
(ΛEË
) return0
or1 + length(xs)
. -
any
,elem
,oelem
and variants (V€£
) return the index of the first element that satisfies the predicate, or0
is one doesn't exist. - Character predicates, like
isuppr
, return either0
or the codepoint of the argument.
Numeric values can be of three kinds: arbitrary precision rational numbers (which includes integers), double precision floats, or special values.
The last kind consists of positive and negative infinities and the special value Any
, which corresponds to NaN
in more conventional languages, and is the result of 0/0.
Any
is considered to be equal to all other numbers.
Numeric functions generally conserve the types of their arguments, casting rational numbers to floats if necessary.
For example, div
(/
) returns a rational number or special value if its arguments are rational, and idiv
(÷
) always returns an integer or a special value.
The rounding functions floor
and ceil
(⌊⌈
) also return an integer or a special value.
Most numeric functions support infinite arguments, although their behavior may not make sense from a mathematical point of view.
Every Husk type has a pre-defined default value that's used as a placeholder in some cases, like indexing into an empty list, and in the function prep0
(Θ
), which prepends a default value to a list.
The default numeric value is 0
, the default character is a space, the default list is an empty list, and the default tuple is a pair of default values of the respective types.
This means that the default value of a concrete type is always falsy.
For function types, the default value is a function that ignores its argument and returns the default value of the return type.
Concrete types also have pre-defined minimum and maximum values, which are used when applying maxl
or minl
(▲▼
) to empty lists.
For numbers, these are negative and positive infinity, and for characters, the null byte and the maximum Unicode character.
The minimum list is the empty list, while the maximum list is an infinite list of maximum values.
For tuples, these values are again defined componentwise.
Some functions, like countf
and groupBy
(#ġ
), take functions as arguments and return new functions as results; we call them higher order functions.
For example, groupBy
takes an equality predicate and a list, and splits the list into chunks of equal elements.
Sometimes it's worthwhile to apply groupBy
on a function that's not semantically an equality predicate, and for that, it's good to know how groupBy
is implemented.
Here are some detailed descriptions of higher order functions.
-
groupBy
(ġ
) takes a predicatep
and a listxs
, and splitsxs
into chunks between each pair of adjacent elementsx
andy
for whichp x y
is falsy. -
nubby
(ü
) takes a predicatep
and a listxs
, and iterates throughxs
from left to right, removing some elements. An elementy
is removed ifp x y
holds for some earlier elementx
that was not removed. -
sortby
(Ö
) takes a predicatep
and a listxs
, and sortsxs
usingp x y
as a stand-in for "x
is greater thany
". More formally,xs
is sorted in a stable way, comparing for eachx
the number of elementsy
for whichp x y
is truthy. -
minlby
(◄
) take a predicatep
and a listxs
, and returns an elementx
that minimizes the number of elementsy
for whichp x y
is truthy.maxlby
(►
) is similar, but maximizes the number. -
sameby
(Ë
) takes a predicatep
and a listxs
. It returns1 + length(xs)
ifp x y
holds for all pairsx, y
occurring inxs
in this order (not necessarily adjacent), and0
otherwise. -
keyby
(k
) takes a predicatep
and a listxs
, and separates it into (possibly non-contiguous) subsequences for whichË p
holds. The algorithm is greedy: the first subsequence in the result contains the headx
ofxs
, then the first elementy
afterx
for whichp x y
holds, then the first elementz
aftery
for whichp x z
andp y z
hold, and so on. The skipped elements are used in the next subsequences. -
onixes
(η
) takes a higher-order functionf
and a listxs
, and appliesf
to the function that indexes intoxs
, and the list of indices ofxs
. Some common use cases includeηġ
, which groups the indices of a list by its values, andηf
, which computes the indices of truthy elements.
Some higher order functions are called combinators, since their main purpose is to combine two or more functions together in a generic way, or in general to provide the "plumbing" of flow control.
Here is a (possibly incomplete) list of combinators and their semantics.
The letters f g h k
stand for functions and x y z u
their arguments.
-
com
(o
) is function composition:(o f g) x
meansf (g x)
.com2
,com3
andcom4
, which share the same symbol, are defined mimilarly but with more arguments tog
:(o f g) x y
meansf (g x y)
,(o f g) x y z
meansf (g x y z)
and(o f g) x y z u
meansf (g x y z u)
. The correct implementation is inferred from context. -
ȯ f g h
is equivalent too f (o g h)
and composes three functions. -
ö f g h k
is equivalent too f (o g (o h k))
and composes four functions. -
comf
(·
) is function composition for the second argument:· f g x y
meansf x (g y)
. The variantscomf2
,comf3
andcomf4
assume thatg
has higher arity: for example,· f g x y z u
meansf x (g y z u)
. -
id
(I
) is the identity function. -
const
(K
) takes two arguments and returns the second one. When applied partially,K x
is a function that takes one argument, ignores it and returnsx
. -
hook
(S
) is the S-combinator:S f g x
meansf x (g x)
. -
bhook
(S
) is the S-combinator with an extra argument:S f g x y
meansf x (g x y)
. -
hookf
(Ṡ
) is a flipped S-combinators:Ṡ f g x
meansf (g x) x
. -
bhookf
(Ṡ
) ishookf
with an extra argument:Ṡ f g x y
meansf (g x y) y
. -
flip
(`
) changes the argument order of a binary function:` f x y
meansf y x
. -
argdup
(´
) duplicates an argument:´ f x
meansf x x
. -
fork
(§
) applies two functions to one value and combines the results:§ f g h x
meansf (g x) (h x)
. -
fork2
(§
) isfork
with an extra argument:§ f g h x y
meansf (g x y) (h x y)
. -
combin
(¤
) applies one function to two values and combines the results:¤ f g x y
meansf (g x) (g y)
. -
branch
(~
) applies two functions to two values and combines the results:~ f g h x y
meansf (g x) (h y)
.