data Vector length a where
Empty :: Vector 0 a
Cons :: a -> Vector n a -> Vector (1 + n) a
But Haskell isn't very good at such encodings. Type-level computation is often not worth it.That said, even NonEmptyList is sometimes useful. For example, some Prelude functions could use it:
group :: [a] -> [NonEmptyList a]
Making common idioms like: map head . group ...
Safe again.Not sure what you mean by:
> How could you get the last element from your NonEmptyList? How could you tell how many elements in it?) Exactly two.
import Data.Monoid
import Data.Maybe
lastNel :: NonEmptyList a -> a
lastNel (NEL x xs) = fromMaybe x . getLast $ mconcat $ map (Last . Just) xs
lengthNel :: NonEmptyList a -> Int
lengthNel (NEL x xs) = 1 + length xs> Cons :: a -> Vector n a --> Vector (1 + n) a
This makes no sense, you can't specify constants in a type signature, and you certainly can't add constants to a type variable in one.
I may be the one not in the know here, if so please show me this magic.
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
data Nat = Z | S Nat
data Vector l a where
Nil :: Vector Z a
Cons :: a -> Vector l a -> Vector (S l) aIs your problem mainly what you call this notion?
data NEL a = One a | More a (NEL a)
but then you have to write fresh functions for all of the default list methods without any performance improvements (which make doing so totally valuable for things like Vector). You also have NEL being an instance of a more general NonEmptyFunctor pattern like in (http://hackage.haskell.org/packages/archive/non-empty/0.1.3/...).With this recursive NEL, last is
last :: NEL a -> a
last (One a) = a
last (More _ more) = last more
and (inefficient, corecursive) length is len :: NEL a -> Int
len (One _) = 1
len (More _ more) = succ (len more)
NELs are quite useful not just for safety. head as type [a] -> a is largely considered to be a mistake, the Safe package is quite popular and redefines head as having type [a] -> Maybe a. I use it frequently.NELs have properties like being Semigroups (and not Monoids) and Comonads which regular lists do not. This helps not only for theoretical guarantees of safety but also so that we can feel confident that our typeclass declarations have the meaning they're supposed to have.
So is (NEL a = NEL a [a]) a bad solution? It's perhaps less independently beautiful than the truly recursive NEL, but it's easier to write and takes advantage of Haskell's built in "possibly empty List" functionality. It's also more "globally beautiful" in that it fits into the family of types "non-empty functors". The recursive version is also trivially isomorphic, so there's no loss in functionality.
head :: [a] -> a
I would code it as: head :: [a] -> Maybe a
returning Nothing for empty lists. Same applies to tail.But others have very good reasons to disagree: http://stackoverflow.com/questions/6364409/why-does-haskells...
In the comments on Real World Haskell people (Alex Stangl and Paul Johnson in particular) are talking about added complexity of deferring invariant errors, but since these are type-declared via `Maybe` it really helps to add safety. I personally have written many, many functions with partial types because I had forgotten about some assumed invariants and had them fixed by use of `safeHead`.
NonEmptyList is pretty good for pre-handling all of the failure modes.
Keep in mind that this is a structured 100-level class targeted at undergrads who are relatively new to programming and haven't seen much in the way of functional programming and Hindley-Milner typing.
I don't think so: http://en.wikipedia.org/wiki/List_(abstract_data_type)
It begins with head is a mistake! It should not be in the Prelude. Other partial Prelude functions you should almost never use include tail, init, last, and (!!). From this point on, using one of these functions on a homework assignment will lose style points!
And here is a proposal:
Dear sirs, a List is a recursive data structure by definition. Non-recursive List is an unimaginable nonsense. What was made here with a name of safe(!) NonEmptyList is some ugly Pair with lots of syntactic noise.How could you get the last element from your NonEmptyList? How could you tell how many elements in it?)
But, of course, never ever use these ugly unsafe lists - they might be empty! Use safe NonEmptyList because in Haskell everything is safe. And never try to think what the fuck you are reading.