Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Efficient Binary Multiplication (Steven Leiva)
----------------------------------------------------------------------
Message: 1
Date: Sat, 28 Apr 2018 11:08:22 -0500
From: Steven Leiva <leiva.ste...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Efficient Binary Multiplication
Message-ID:
<CA+=woS5xTmROZj1a=awAWSv3Ka_J3q92R=knrs5ig8kkwmt...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Thank you Stephen for the clarification!
On Wed, Apr 18, 2018 at 12:33 PM, Stephen Tetley <stephen.tet...@gmail.com>
wrote:
> List fusion has existed for a long time (based on a change to the
> internal representation of lists to make them streams).
>
> IIRC the actual implementation was not considered a satisfactory
> replacement for GHCs existing list implementation as performance
> improvements were not uniform, the stream representation is good for
> some things worse for others. I don't know whether this situation has
> now changed.
>
> Byte String and Text exist because implementing strings or byte
> sequences as a cons list of Char or Byte is very inefficient both for
> storage / data locality and for many operations. Fusion for Byte
> String and Text is a bonus rather than a motivation.
>
>
> [*] Stream Fusion: From Lists to Streams to Nothing at All
> Duncan Coutts , Roman Leshchinskiy , Don Stewart
> http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401
>
> On 17 April 2018 at 01:48, Steven Leiva <leiva.ste...@gmail.com> wrote:
> > Interesting question.
> >
> > So there is a concept in computer science called fusion.
> >
> > My understanding (I don't have a CS degree) is that when data is subject
> to
> > fusion, we don't create the intermediary lists as you are talking about.
> > This is why, in Haskell, we have the ByteString and Text datatypes.
> Unlike
> > String, they (ByteString / Text) are subject to fusion. Text is useful
> when
> > we are dealing with unicode data, while ByteString is the correct tool
> when
> > we are dealing with binary data.
> >
> > All of this is to say that you should look at the ByteString data type.
> > (Take a look at this description, for example:
> > https://hackage.haskell.org/package/bytestring-0.10.8.2/
> docs/Data-ByteString.html#t:ByteString).
> >
> > The only potential problem I see is that ByteString internally uses
> Word8,
> > and since Word8 is unsigned, negatives are problematic. (Now that I think
> > about it, how the heck do you represent negative numbers in binary?).
> >
> > I hope this is useful.
> >
> > On Sat, Apr 14, 2018 at 4:28 PM, Quentin Liu <quentin.liu.0...@gmail.com
> >
> > wrote:
> >>
> >> Hi all,
> >>
> >> Suppose I want to multiply two binary numbers whose representation uses
> >> lists (e.g. 14 is represented as [1, 1, 1, 0]). Is there any efficient
> way
> >> to do binary multiplication? The way I could come up with involves a
> lot of
> >> intermediate lists that will be discarded eventually and is extremely
> >> inefficient. I know one fast algorithm that uses Array but would it be
> >> possible to do the multiplication with only lists?
> >>
> >> Regards,
> >> Qingbo Liu
> >>
> >> _______________________________________________
> >> Beginners mailing list
> >> Beginners@haskell.org
> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> >>
> >
> >
> >
> > --
> > Steven Leiva
> > 305.528.6038
> > leiva.ste...@gmail.com
> > http://www.linkedin.com/in/stevenleiva
> >
> > _______________________________________________
> > Beginners mailing list
> > Beginners@haskell.org
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> >
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
--
Steven Leiva
305.528.6038
leiva.ste...@gmail.com
http://www.linkedin.com/in/stevenleiva
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20180428/f5ecf601/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 118, Issue 13
******************************************
