<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div style="" data-md-original="<div
class="moz-cite-prefix">One solution would be to fold
over a specific semigroup instead of a recursive
function:<br>```haskell<br>import
Data.Semigroup<br>import Data.Foldable
(foldMap)<br>import Data.Maybe
(maybeToList)<br><br>data Darle a = Darle { getInit ::
[a], getLast :: a }<br>&nbsp; deriving
Show<br>instance Semigroup (Darle a)
where<br>&nbsp;&nbsp;&nbsp; ~(Darle xs1 l1)
&lt;&gt; ~(Darle xs2 l2) = Darle (xs1 ++ [l1] ++ xs2)
l2<br><br>darle :: [a] -&gt; Darle
a<br>darle = foldr1 (&lt;&gt;) . map (Darle
[])<br>```<br>It's somewhat more verbose, but the core
idea is clearly expressed in the one line that defines
`&lt;&gt;`, and IMHO it better shows _what_ are we doing
rather than _how_. It's sufficiently lazy so that you can do
something like `head . getInit $ darle
[1..]`.<br><br>&nbsp; Best
regards,<br>&nbsp; Petr<br><br>Dne
08/30/2013 08:18 PM, Lucas Paul
napsal(a):<br></div><blockquote
cite="mid:CAMvcYxAacBw9u0B82Jih1VfuCnbFGNFYzNvNPtmHWSCd+zvo3w@mail.gmail.com"
type="cite"><pre wrap="">Suppose I
need to get an element from a data structure, and also
modify the data structure. For example, I might need to get and
delete
the last element of a list:
darle xs = ((last xs), (rmlast xs)) where rmlast [_] = [] rmlast
(y:ys) = y:(rmlast ys)
There are probably other and better ways to write rmlast, but I
want
to focus on the fact that darle here, for lack of a better name
off
the top of my head, appears to traverse the list twice. Once to
get
the element, and once to remove it to produce a new list. This
seems
bad. Especially for large data structures, I don't want to be
traversing twice to do what ought to be one operation. To fix it,
I
might be tempted to write something like:
darle' [a] = (a, [])
darle' (x:xs) = let (a, ys) = darle' xs in (a, (x:ys))
But this version has lost its elegance. It was also kind of harder
to
come up with, and for more complex data structures (like the
binary
search tree) the simpler expression is really desirable. Can a
really
smart compiler transform/optimize the first definition into
something
that traverses the data structure only once? Can GHC?
- Lucas
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
</pre>
</blockquote><br>" class="markdown-here-wrapper"
id="markdown-here-wrapper-542938">
<p style="margin: 1.2em 0px ! important;">One solution would be to
fold over a specific semigroup instead of a recursive function:</p>
<pre style="font-size: 0.85em; font-family: Consolas,Inconsolata,Courier,monospace;font-size: 1em; line-height: 1.2em; overflow: auto;margin: 1.2em 0px;"><code style="font-size: 0.85em; font-family: Consolas,Inconsolata,Courier,monospace;margin: 0px 0.15em; padding: 0px 0.3em; white-space: nowrap; border: 1px solid rgb(234, 234, 234); background-color: rgb(248, 248, 248); border-radius: 3px 3px 3px 3px; display: inline;white-space: pre; border-radius: 3px 3px 3px 3px; border: 1px solid rgb(204, 204, 204); padding: 0.5em 0.7em;display: block; padding: 0.5em; color: rgb(51, 51, 51); background: none repeat scroll 0% 0% rgb(248, 248, 255);" class="language-haskell"><span class="import"><span style="color: rgb(51, 51, 51); font-weight: bold;" class="keyword">import</span> Data.Semigroup</span>
<span class="import"><span style="color: rgb(51, 51, 51); font-weight: bold;" class="keyword">import</span> Data.Foldable <span class="container">(<span style="color: rgb(153, 0, 0); font-weight: bold;" class="title">foldMap</span>)</span></span>
<span class="import"><span style="color: rgb(51, 51, 51); font-weight: bold;" class="keyword">import</span> Data.Maybe <span class="container">(<span style="color: rgb(153, 0, 0); font-weight: bold;" class="title">maybeToList</span>)</span></span>
<span class="typedef"><span style="color: rgb(51, 51, 51); font-weight: bold;" class="keyword">data</span> <span class="type">Darle</span> a = <span class="type">Darle</span> <span class="container">{ <span style="color: rgb(153, 0, 0); font-weight: bold;" class="title">getInit</span> :: [<span style="color: rgb(153, 0, 0); font-weight: bold;" class="title">a</span>], <span style="color: rgb(153, 0, 0); font-weight: bold;" class="title">getLast</span> :: <span style="color: rgb(153, 0, 0); font-weight: bold;" class="title">a</span> }</span></span>
<span style="color: rgb(51, 51, 51); font-weight: bold;" class="keyword">deriving</span> <span class="type">Show</span>
<span style="color: rgb(68, 85, 136); font-weight: bold;" class="class"><span style="color: rgb(51, 51, 51); font-weight: bold;" class="keyword">instance</span> <span class="type">Semigroup</span> (<span class="type">Darle</span> a) <span style="color: rgb(51, 51, 51); font-weight: bold;" class="keyword">where</span></span>
~(<span class="type">Darle</span> xs1 l1) <> ~(<span class="type">Darle</span> xs2 l2) = <span class="type">Darle</span> (xs1 ++ [l1] ++ xs2) l2
<span style="color: rgb(153, 0, 0); font-weight: bold;" class="title">darle</span> :: [a] -> <span class="type">Darle</span> a
<span style="color: rgb(153, 0, 0); font-weight: bold;" class="title">darle</span> = foldr1 (<>) . map (<span class="type">Darle</span> [])</code></pre>
<p style="margin: 1.2em 0px ! important;">It's somewhat more
verbose, but the core idea is clearly expressed in the one line
that defines <code style="font-size: 0.85em; font-family:
Consolas,Inconsolata,Courier,monospace;margin: 0px 0.15em;
padding: 0px 0.3em; white-space: nowrap; border: 1px solid
rgb(234, 234, 234); background-color: rgb(248, 248, 248);
border-radius: 3px 3px 3px 3px; display: inline;"><></code>,
and IMHO it better shows <em>what</em> are we doing rather than
<em>how</em>. It's sufficiently lazy so that you can do
something like <code style="font-size: 0.85em; font-family:
Consolas,Inconsolata,Courier,monospace;margin: 0px 0.15em;
padding: 0px 0.3em; white-space: nowrap; border: 1px solid
rgb(234, 234, 234); background-color: rgb(248, 248, 248);
border-radius: 3px 3px 3px 3px; display: inline;">head .
getInit $ darle [1..]</code>.</p>
<p style="margin: 1.2em 0px ! important;"> Best regards,<br>
Petr</p>
<p style="margin: 1.2em 0px ! important;">Dne 08/30/2013 08:18 PM,
Lucas Paul napsal(a):</p>
<p style="margin: 1.2em 0px ! important;"></p>
<div class="markdown-here-exclude">
<p></p>
<blockquote
cite="mid:CAMvcYxAacBw9u0B82Jih1VfuCnbFGNFYzNvNPtmHWSCd+zvo3w@mail.gmail.com"
type="cite">
<pre wrap="">Suppose I need to get an element from a data structure, and also
modify the data structure. For example, I might need to get and delete
the last element of a list:
darle xs = ((last xs), (rmlast xs)) where
rmlast [_] = []
rmlast (y:ys) = y:(rmlast ys)
There are probably other and better ways to write rmlast, but I want
to focus on the fact that darle here, for lack of a better name off
the top of my head, appears to traverse the list twice. Once to get
the element, and once to remove it to produce a new list. This seems
bad. Especially for large data structures, I don't want to be
traversing twice to do what ought to be one operation. To fix it, I
might be tempted to write something like:
darle' [a] = (a, [])
darle' (x:xs) = let (a, ys) = darle' xs in (a, (x:ys))
But this version has lost its elegance. It was also kind of harder to
come up with, and for more complex data structures (like the binary
search tree) the simpler expression is really desirable. Can a really
smart compiler transform/optimize the first definition into something
that traverses the data structure only once? Can GHC?
- Lucas
_______________________________________________
Haskell-Cafe mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a>
</pre>
</blockquote>
<p></p>
</div>
<p style="margin: 1.2em 0px ! important;"></p>
</div>
</body>
</html>