Difference between revisions of "99 questions/Solutions/3"
< 99 questions | Solutions
Jump to navigation
Jump to search
m (Fix a typo: elementAt -> elementAt'') |
|||
(7 intermediate revisions by 6 users not shown) | |||
Line 13: | Line 13: | ||
<haskell> |
<haskell> |
||
elementAt :: [a] -> Int -> a |
elementAt :: [a] -> Int -> a |
||
− | elementAt list i = list !! (i-1) |
+ | elementAt list i = list !! (i-1) |
</haskell> |
</haskell> |
||
Line 20: | Line 20: | ||
<haskell> |
<haskell> |
||
elementAt' :: [a] -> Int -> a |
elementAt' :: [a] -> Int -> a |
||
− | elementAt' (x:_) 1 = x |
+ | elementAt' (x:_) 1 = x |
− | elementAt' [] _ = error "Index out of bounds" |
+ | elementAt' [] _ = error "Index out of bounds" |
elementAt' (_:xs) k |
elementAt' (_:xs) k |
||
− | + | | k < 1 = error "Index out of bounds" |
|
− | + | | otherwise = elementAt' xs (k - 1) |
|
</haskell> |
</haskell> |
||
Line 31: | Line 31: | ||
<haskell> |
<haskell> |
||
elementAt'' :: [a] -> Int -> a |
elementAt'' :: [a] -> Int -> a |
||
− | elementAt'' (x:_) 1 = x |
+ | elementAt'' (x:_) 1 = x |
elementAt'' (_:xs) i = elementAt'' xs (i - 1) |
elementAt'' (_:xs) i = elementAt'' xs (i - 1) |
||
− | elementAt'' _ _ = error "Index out of bounds" |
+ | elementAt'' _ _ = error "Index out of bounds" |
</haskell> |
</haskell> |
||
'''This does not work correctly on invalid indexes and infinite lists, e.g.:''' |
'''This does not work correctly on invalid indexes and infinite lists, e.g.:''' |
||
Line 43: | Line 43: | ||
<haskell> |
<haskell> |
||
+ | elementAt'' xs n |
||
⚫ | |||
+ | | length xs < n = error "Index out of bounds" |
||
− | -- Main> map (elementAt_w' [1..4]) [1..10] |
||
+ | | otherwise = fst . last $ zip xs [1..n] |
||
− | -- [1,2,3,4,4,4,4,4,4,4] |
||
⚫ | |||
⚫ | |||
⚫ | |||
+ | $ replicate (n - 1) tail |
||
⚫ | |||
+ | -- Negative indices not handled correctly: |
||
− | -- Main> map (elementAt_w'' [1..4]) [1..10] |
||
+ | -- Main> elementAt''' "haskell" (-1) |
||
− | -- [1,2,3,4,4,4,4,4,4,4] |
||
+ | -- 'h' |
||
− | </haskell> |
||
+ | |||
+ | elementAt'''' xs n |
||
+ | | length xs < n = error "Index out of bounds" |
||
+ | | otherwise = last $ take n xs |
||
+ | |||
+ | elementAt''''' xs n |
||
+ | | length xs < n = error "Index out of bounds" |
||
⚫ | |||
+ | |||
+ | elementAt'''''' xs n |
||
+ | | length xs < n = error "Index out of bounds" |
||
+ | | otherwise = head $ drop (n - 1) xs |
||
− | <haskell> |
||
⚫ | |||
</haskell> |
</haskell> |
||
Line 62: | Line 71: | ||
elementAt_w'pf = (last .) . take . (+ 1) |
elementAt_w'pf = (last .) . take . (+ 1) |
||
</haskell> |
</haskell> |
||
+ | |||
+ | Pedantic note: the above definition of <hask>elementAt_w'pf</hask> does not conform to the order of arguments specified by the question, but the following does: |
||
⚫ | |||
⚫ | |||
⚫ | |||
+ | |||
+ | |||
+ | [[Category:Programming exercise spoilers]] |
Latest revision as of 02:32, 15 June 2016
(*) Find the K'th element of a list. The first element in the list is number 1.
This is (almost) the infix operator !! in Prelude, which is defined as:
(!!) :: [a] -> Int -> a
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n-1)
Except this doesn't quite work, because !! is zero-indexed, and element-at should be one-indexed. So:
elementAt :: [a] -> Int -> a
elementAt list i = list !! (i-1)
Or without using the infix operator:
elementAt' :: [a] -> Int -> a
elementAt' (x:_) 1 = x
elementAt' [] _ = error "Index out of bounds"
elementAt' (_:xs) k
| k < 1 = error "Index out of bounds"
| otherwise = elementAt' xs (k - 1)
Alternative version:
elementAt'' :: [a] -> Int -> a
elementAt'' (x:_) 1 = x
elementAt'' (_:xs) i = elementAt'' xs (i - 1)
elementAt'' _ _ = error "Index out of bounds"
This does not work correctly on invalid indexes and infinite lists, e.g.:
elementAt'' [1..] 0
A few more solutions using prelude functions:
elementAt'' xs n
| length xs < n = error "Index out of bounds"
| otherwise = fst . last $ zip xs [1..n]
elementAt''' xs n = head $ foldr ($) xs
$ replicate (n - 1) tail
-- Negative indices not handled correctly:
-- Main> elementAt''' "haskell" (-1)
-- 'h'
elementAt'''' xs n
| length xs < n = error "Index out of bounds"
| otherwise = last $ take n xs
elementAt''''' xs n
| length xs < n = error "Index out of bounds"
| otherwise = head . reverse $ take n xs
elementAt'''''' xs n
| length xs < n = error "Index out of bounds"
| otherwise = head $ drop (n - 1) xs
or elementAt_w'
correctly in point-free style:
elementAt_w'pf = (last .) . take . (+ 1)
Pedantic note: the above definition of elementAt_w'pf
does not conform to the order of arguments specified by the question, but the following does:
elementAt_w'pf' = flip $ (last .) . take . (+ 1)