CODEWITHSUNDEEP
haskell
lei_z
lei_z

Reputation: 1107

How to implement the head function using fst function

I admit this is my homework. But I really couldn't find a good solution after working hard on it.

There might be some stupid ways to accomplish this, like:

myHead (x:[]) = x
myHead (x:y:xs) = fst (x, y)

But I don't think that's what the teacher wants.
BTW, error-handling is not required.

Thanks in advance!

Upvotes: 0

Views: 2770

Answers (3)

J. Abrahamson
J. Abrahamson

Reputation: 74364

There's a very natural function that's not in the prelude called "uncons" which is the inverse of uncurried cons.

cons :: a -> [a] -> [a]
uncurry cons :: (a, [a]) -> [a]

uncons :: [a] -> (a, [a])
uncons (x:xs) = (x, xs)

You can use it to implement head as

head = fst . uncons

Why is uncons natural?

You can think of a list as the datatype that's defined through the use of two constructor functions

nil :: [a]
nil = []

cons :: (a, [a]) -> [a]
cons (a,as) = a:as

You can also think of it as the data type which is deconstructed by a function

destruct :: [a] -> Maybe (a, [a])
destruct [] = Nothing
destruct (a:as) = Just (a, as)

It's well beyond this answer to explain why those are so definitively tied to the list type, but one way to look at it is to try to define

nil      :: f a
cons     :: (a, f a) -> f a

or

destruct :: f a -> Maybe (a, f a)

for any other container type f. You'll find that they all have very close relationships with lists.

You can almost already see uncons in the second case of the definition of destruct, but there's a Just in the way. This is uncons is better paired with head and tail which are not defined on empty lists

head [] = error "Prelude.head"

so we can adjust the previous answer to work for infinite streams. Here we can think of infinite streams as being constructed by one function

data Stream a = Next a (Stream a)

cons :: (a, Stream a) -> Stream a
cons (a, as) = Next a as

and destructed by one function

uncons :: Stream a -> (a, Stream a)
uncons (Next a as) = (a, as)

-- a. k. a.
uncons stream = (head stream, tail stream)

the two being inverses of one another.

Now we can get head for Streams by getting the first element of the return tuple from uncons

head = fst . uncons

And that's what head models in the Prelude, so we can pretend like lists are infinite streams and define head in that way

uncons :: [a] -> (a, [a])
uncons (a:as) = (a, as)

-- a. k. a.
uncons list = (head list, tail list)

head = fst . uncons

Upvotes: 5

Peter Hall
Peter Hall

Reputation: 58785

Perhaps you're expected write to your own cons List type, then it might make more sense. Although type synonyms can't be recursive, so you end up using a non-tuple data constructor, making the tuple superfluous.. it would look like:

data List a = Nil | List (a, List a)
        deriving( Show )

head :: List a -> a
head (List c) = fst c

Upvotes: 2

leftaroundabout
leftaroundabout

Reputation: 120731

Like already said in the comments, this is just a silly task and you won't get something you could call a good implementation of head.

Your solution, for those requirements, is just fine – as the only change I would replace (x:y:xs) with (x:y:_) since xs isn't used at all (which would actually cause a compiler warning in some settings). In fact, you could do that with y as well:

myHead (x:_:_) = fst (x, undefined)

There would be alternatives that look perhaps not quite so useless use of fst, i.e. don't just build a tuple by hand and immediately deconstruct it again:

myHead' [x] = x
myHead' xs = myHead' . fst $ splitAt 1 xs

myHead'' = foldr1 $ curry fst

myHead''' = fromJust . find ((==0) . fst) . zip [0..]

but you could rightfully say that these are just ridiculous.

Upvotes: 1

Related Questions