<div dir="ltr">Thank you Stephen for the clarification!</div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 18, 2018 at 12:33 PM, Stephen Tetley <span dir="ltr"><<a href="mailto:stephen.tetley@gmail.com" target="_blank">stephen.tetley@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">List fusion has existed for a long time (based on a change to the<br>
internal representation of lists to make them streams).<br>
<br>
IIRC the actual implementation was not considered a satisfactory<br>
replacement for GHCs existing list implementation as performance<br>
improvements were not uniform, the stream representation is good for<br>
some things worse for others. I don't know whether this situation has<br>
now changed.<br>
<br>
Byte String and Text exist because implementing strings or byte<br>
sequences as a cons list of Char or Byte is very inefficient both for<br>
storage / data locality and for many operations. Fusion for Byte<br>
String and Text is a bonus rather than a motivation.<br>
<br>
<br>
[*] Stream Fusion: From Lists to Streams to Nothing at All<br>
Duncan Coutts , Roman Leshchinskiy , Don Stewart<br>
<a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401" rel="noreferrer" target="_blank">http://citeseer.ist.psu.edu/<wbr>viewdoc/summary?doi=10.1.1.<wbr>104.7401</a><br>
<div class="HOEnZb"><div class="h5"><br>
On 17 April 2018 at 01:48, Steven Leiva <<a href="mailto:leiva.steven@gmail.com">leiva.steven@gmail.com</a>> wrote:<br>
> Interesting question.<br>
><br>
> So there is a concept in computer science called fusion.<br>
><br>
> My understanding (I don't have a CS degree) is that when data is subject to<br>
> fusion, we don't create the intermediary lists as you are talking about.<br>
> This is why, in Haskell, we have the ByteString and Text datatypes. Unlike<br>
> String, they (ByteString / Text) are subject to fusion. Text is useful when<br>
> we are dealing with unicode data, while ByteString is the correct tool when<br>
> we are dealing with binary data.<br>
><br>
> All of this is to say that you should look at the ByteString data type.<br>
> (Take a look at this description, for example:<br>
> <a href="https://hackage.haskell.org/package/bytestring-0.10.8.2/docs/Data-ByteString.html#t:ByteString" rel="noreferrer" target="_blank">https://hackage.haskell.org/<wbr>package/bytestring-0.10.8.2/<wbr>docs/Data-ByteString.html#t:<wbr>ByteString</a>).<br>
><br>
> The only potential problem I see is that ByteString internally uses Word8,<br>
> and since Word8 is unsigned, negatives are problematic. (Now that I think<br>
> about it, how the heck do you represent negative numbers in binary?).<br>
><br>
> I hope this is useful.<br>
><br>
> On Sat, Apr 14, 2018 at 4:28 PM, Quentin Liu <<a href="mailto:quentin.liu.0415@gmail.com">quentin.liu.0415@gmail.com</a>><br>
> wrote:<br>
>><br>
>> Hi all,<br>
>><br>
>> Suppose I want to multiply two binary numbers whose representation uses<br>
>> lists (e.g. 14 is represented as [1, 1, 1, 0]). Is there any efficient way<br>
>> to do binary multiplication? The way I could come up with involves a lot of<br>
>> intermediate lists that will be discarded eventually and is extremely<br>
>> inefficient. I know one fast algorithm that uses Array but would it be<br>
>> possible to do the multiplication with only lists?<br>
>><br>
>> Regards,<br>
>> Qingbo Liu<br>
>><br>
>> ______________________________<wbr>_________________<br>
>> Beginners mailing list<br>
>> <a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
>> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/beginners</a><br>
>><br>
><br>
><br>
><br>
> --<br>
> Steven Leiva<br>
> 305.528.6038<br>
> <a href="mailto:leiva.steven@gmail.com">leiva.steven@gmail.com</a><br>
> <a href="http://www.linkedin.com/in/stevenleiva" rel="noreferrer" target="_blank">http://www.linkedin.com/in/<wbr>stevenleiva</a><br>
><br>
> ______________________________<wbr>_________________<br>
> Beginners mailing list<br>
> <a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/beginners</a><br>
><br>
______________________________<wbr>_________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/beginners</a><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">Steven Leiva<br>305.528.6038<br><a href="mailto:leiva.steven@gmail.com" target="_blank">leiva.steven@gmail.com</a><br><a href="http://www.linkedin.com/in/stevenleiva" target="_blank">http://www.linkedin.com/in/stevenleiva</a><br></div>
</div>