https://wiki.haskell.org/api.php?action=feedcontributions&user=Trackbully&feedformat=atomHaskellWiki - User contributions [en]2024-03-29T07:12:10ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=99_questions/Solutions/21&diff=4382099 questions/Solutions/212012-01-04T22:21:17Z<p>Trackbully: </p>
<hr />
<div>Insert an element at a given position into a list.<br />
<br />
<haskell><br />
insertAt :: a -> [a] -> Int -> [a]<br />
insertAt x xs (n+1) = let (ys,zs) = split xs n in ys++x:zs<br />
</haskell><br />
or<br />
<haskell><br />
insertAt :: a -> [a] -> Int -> [a]<br />
insertAt x ys 1 = x:ys<br />
insertAt x (y:ys) n = y:insertAt x ys (n-1)<br />
</haskell><br />
<br />
There are two possible simple solutions. First we can use <hask>split</hask> from problem 17 (or even <hask>splitAt</hask> from the Prelude) to split the list and insert the element. Second we can define a recursive solution on our own.<br />
<br />
As a note to the above solution - this presumes that the inserted argument will be a singleton type <tt>a</tt> inserted into a list <tt>[a]</tt>. The lisp example does not infer this intent. As a result, presuming the data to be inserted is likewise of type <tt>[a]</tt> (which we are tacitly inferring here to be String into String insertion), a solution is:<br />
<br />
<haskell><br />
insertAt x xs n = take (n-1) xs ++ [x] ++ drop (n-1) xs<br />
</haskell><br />
<br />
This solution, like many others in this quiz presumes counting element positions starts at 1, perhaps causing needless confusion.<br />
<br />
A solution using foldl and a closure, also assumes lists are 1 indexed:<br />
<haskell><br />
insertAt :: a -> [a] -> Int -> [a]<br />
insertAt el lst n = fst $ foldl helper ([],1) lst<br />
where helper (acc,i) x = if i == n then (acc++[el,x],i+1) else (acc++[x],i+1)<br />
</haskell></div>Trackbullyhttps://wiki.haskell.org/index.php?title=99_questions/Solutions/18&diff=4381999 questions/Solutions/182012-01-04T21:54:59Z<p>Trackbully: </p>
<hr />
<div>(**) Extract a slice from a list.<br />
<br />
Given two indices, i and k, the slice is the list containing the elements between the i'th and k'th element of the original list (both limits included). Start counting the elements with 1.<br />
<br />
<haskell><br />
slice xs i k | i>0 = take (k-i+1) $ drop (i-1) xs<br />
</haskell><br />
<br />
The same solution as above, but the more paranoid (maybe too paranoid?) version of it (uses guards and Maybe):<br />
<br />
<haskell><br />
slice :: [a] -> Int -> Int -> Maybe [a]<br />
slice [] _ _ = Just []<br />
slice xs k n | k == n = Just []<br />
| k > n || k > length xs || <br />
n > length xs || k < 0 || n < 0 = Nothing<br />
| k == 0 = Just (take n xs)<br />
| otherwise = Just (drop (k-1) $ take n xs)<br />
</haskell><br />
<br />
Or, an iterative solution:<br />
<br />
<haskell><br />
slice :: [a]->Int->Int->[a]<br />
slice lst 1 m = slice' lst m []<br />
where<br />
slice' :: [a]->Int->[a]->[a]<br />
slice' _ 0 acc = reverse acc<br />
slice' (x:xs) n acc = slice' xs (n - 1) (x:acc)<br />
slice (x:xs) n m = slice xs (n - 1) (m - 1)<br />
</haskell><br />
<br />
Or:<br />
<br />
<haskell><br />
slice :: [a] -> Int -> Int -> [a]<br />
slice (x:xs) i k<br />
| i > 1 = slice xs (i - 1) (k - 1)<br />
| k < 1 = []<br />
| otherwise = x:slice xs (i - 1) (k - 1)<br />
</haskell><br />
<br />
Another way using <hask>splitAt</hask>, though not nearly as elegant as the <hask>take</hask>&nbsp;and <hask>drop</hask>&nbsp;version:<br />
<br />
<haskell><br />
slice :: [a] -> Int -> Int -> [a]<br />
slice xs i k = chunk<br />
where chop = snd $ splitAt i' xs -- Get the piece starting at i<br />
chunk = fst $ splitAt (k - i') chop -- Remove the part after k<br />
i' = i - 1<br />
</haskell><br />
A little cleaner, using the previous problem's split (a.k.a. <hask>splitAt</hask>):<br />
<haskell><br />
slice xs (i+1) k = snd (split (fst (split xs k)) i)<br />
</haskell><br />
<br />
A solution using <hask>zip</hask>, <hask>filter</hask>&nbsp;then <hask>map</hask>&nbsp;seems straight-forward to me (''NB: this won't work for infinite lists''):<br />
<br />
<haskell><br />
slice xs i j = map snd<br />
$ filter (\(x,_) -> x >= i && x <= j)<br />
$ zip [1..] xs <br />
</haskell><br />
A solution using list comprehension:<br />
<haskell><br />
slice xs i k = [x | (x,j) <- zip xs [1..k], i <= j]<br />
</haskell><br />
Another simple solution using take and drop:<br />
<haskell><br />
slice :: [a] -> Int -> Int -> [a]<br />
slice l i k <br />
| i > k = []<br />
| otherwise = (take (k-i+1) (drop (i-1) l))<br />
</haskell></div>Trackbullyhttps://wiki.haskell.org/index.php?title=99_questions/Solutions/81&diff=4381499 questions/Solutions/812012-01-04T17:10:19Z<p>Trackbully: Add an additional recursive solution to the problem</p>
<hr />
<div>(**) Path from one node to another one<br />
<br />
Write a function that, given two nodes a and b in a graph, returns all the acyclic paths from a to b.<br />
<br />
<haskell><br />
import List (elem)<br />
<br />
paths :: Eq a => a -> a -> [(a,a)] -> [[a]]<br />
paths a b g = paths1 a b g []<br />
<br />
paths1 :: Eq a => a -> a -> [(a,a)] -> [a] -> [[a]]<br />
paths1 a b g current = paths2 a b g current [ y | (x,y) <- g, x == a ]<br />
<br />
paths2 :: Eq a => a -> a -> [(a,a)] -> [a] -> [a] -> [[a]]<br />
paths2 a b g current [] | a == b = [current++[b]]<br />
| otherwise = []<br />
paths2 a b g current (x:xs) | a == b = [current++[b]] <br />
| elem a current = []<br />
| otherwise = (paths1 x b g (current++[a])) ++ (paths2 a b g current xs)<br />
</haskell><br />
<br />
This solution uses a representation of a (directed) graph as a list of arcs (a,b).<br />
<br />
----<br />
<br />
Here is another implementation using List's monadic behavior<br />
<br />
<haskell><br />
import Data.List (partition)<br />
<br />
pathsImpl :: Eq a => [a] -> a -> a -> [(a, a)] -> [[a]]<br />
pathsImpl trail src dest clauses<br />
| src == dest = [src:trail]<br />
| otherwise = do<br />
let (nexts, rest) = partition ((==src) . fst) clauses<br />
next <- nexts<br />
pathsImpl (src:trail) (snd next) dest rest<br />
<br />
paths :: Eq a => a -> a -> [(a, a)] -> [[a]]<br />
paths src dest clauses = map reverse (pathsImpl [] src dest clauses)<br />
</haskell><br />
<br />
----<br />
<br />
Here is another recursive implementation <br />
<haskell><br />
paths :: Eq a =>a -> a -> [(a,a)] -> [[a]] <br />
paths source sink edges <br />
| source == sink = [[sink]]<br />
| otherwise = [<br />
[source] ++ path | edge<-edges, (fst edge) == source,<br />
path<-(paths (snd edge) sink [e|e<-edges, e/=edge])<br />
]; <br />
</haskell></div>Trackbully