Personal tools

99 questions/Solutions/20

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
(Added another solution that also indicates failure using Maybe (thanks to zygoloid from #haskell for the input regarding Maybe))
(Edit solution to align with problem statement and example)
 
(5 intermediate revisions by 5 users not shown)
Line 6: Line 6:
 
[] -> error "removeAt: index too large"
 
[] -> error "removeAt: index too large"
 
x:rest -> (x, front ++ rest)
 
x:rest -> (x, front ++ rest)
where (front, back) = splitAt k xs
+
where (front, back) = splitAt (k - 1) xs
 
</haskell>
 
</haskell>
   
Simply use the <hask>splitAt</hask> to split after k elements.
+
Simply use the <hask>splitAt</hask> to split after k - 1 elements.
If the original list has fewer than k+1 elements, the second list will be empty, and there will be no element to extract.
+
If the original list has fewer than k elements, the second list will be empty, and there will be no element to extract.
Note that the Prolog and Lisp versions treat 1 as the first element in the list, and the Lisp version appends NIL elements to the end of the list if k is greater than the list length.
+
Note that we treat 1 as the first element in the list.
   
 
or
 
or
   
 
<haskell>
 
<haskell>
removeAt n xs = (xs!!n,take n xs ++ drop (n+1) xs)
+
removeAt n xs = (xs !! (n - 1), take (n - 1) xs ++ drop n xs)
 
</haskell>
 
</haskell>
   
Line 38: Line 38:
 
where splitted = splitAt nr xs
 
where splitted = splitAt nr xs
 
</haskell>
 
</haskell>
  +
  +
And yet another solution (without error checking):
  +
  +
<haskell>
  +
removeAt :: Int -> [a] -> (a, [a])
  +
removeAt n xs = let (front, back) = splitAt n xs in (last front, init front ++ back)
  +
</haskell>
  +
  +
Similar, point-free style:
  +
  +
<haskell>
  +
removeAt n = (\(a, b) -> (head b, a ++ tail b)) . splitAt (n - 1)
  +
</haskell>
  +
  +
A simple recursive solution:
  +
  +
<haskell>
  +
removeAt 1 (x:xs) = (x, xs)
  +
removeAt n (x:xs) = (l, x:r)
  +
where (l, r) = removeAt (n - 1) xs
  +
</haskell>
  +
  +
  +
[[Category:Programming exercise spoilers]]

Latest revision as of 02:05, 26 February 2014

(*) Remove the K'th element from a list.

removeAt :: Int -> [a] -> (a, [a])
removeAt k xs = case back of
        [] -> error "removeAt: index too large"
        x:rest -> (x, front ++ rest)
  where (front, back) = splitAt (k - 1) xs
Simply use the
splitAt
to split after k - 1 elements.

If the original list has fewer than k elements, the second list will be empty, and there will be no element to extract. Note that we treat 1 as the first element in the list.

or

removeAt n xs = (xs !! (n - 1), take (n - 1) xs ++ drop n xs)

Another solution that avoids throwing an error and using ++ operators. Treats 1 as the first element in the list.

removeAt :: Int -> [a] -> (Maybe a, [a])
removeAt _ [] = (Nothing, [])
removeAt 1 (x:xs) = (Just x, xs)
removeAt k (x:xs) = let (a, r) = removeAt (k - 1) xs in (a, x:r)

Another solution that also uses Maybe to indicate failure:

removeAt :: Int -> [a] -> (Maybe a, [a]) 
removeAt _ [] = (Nothing, [])
removeAt 0 xs = (Nothing, xs)
removeAt nr xs 	| nr > length xs = (Nothing, xs)
		| otherwise = (Just (xs !! nr), fst splitted ++ (tail . snd) splitted)
			where splitted = splitAt nr xs

And yet another solution (without error checking):

removeAt :: Int -> [a] -> (a, [a])
removeAt n xs = let (front, back) = splitAt n xs in (last front, init front ++ back)

Similar, point-free style:

removeAt n = (\(a, b) -> (head b, a ++ tail b)) . splitAt (n - 1)

A simple recursive solution:

removeAt 1 (x:xs) = (x, xs)
removeAt n (x:xs) = (l, x:r)
	where (l, r) = removeAt (n - 1) xs