Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: OrdList implementation (akash g)
2. Re: question about list processing (akash g)
3. Re: question about list processing (akash g)
----------------------------------------------------------------------
Message: 1
Date: Thu, 12 Nov 2015 19:28:44 +0530
From: akash g <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] OrdList implementation
Message-ID:
<CALiga_fiZn4EVpC6YJ=SO=6vjnjayp0c1bk6gw+x9bt91we...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Just a note on the data structure. Wouldn't a binary tree (a balanced one;
red-black, avl etc) give a logarithmic time constant for insertion while a
list will give you a worst case bound of n, n being the length of the list?
https://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Map-Strict.html
:: Data.Map uses a ordered balanced binary tree implementation for storing
and retrieving key value pairs.
Now, with that out of the way,
For 1, you are defining OrdList a to be a new data type (or type with a
data constructor). Just to make sure users of this package cannot
construct ill-formed OrdList, you can hide the constructor and provide your
custom constructor (like fromList and its ilk).
For 2., I don't know what you mean but OrdList is a datatype or rather a
type constructor which takes an additional concrete type to form a concrete
type. In other words, OrdList is of the kind (*->*). Lookup kinds
(wikibooks is good for this and so are http://dev.stephendiehl.com/hask/
and learn you a haskell for great good).
On Thu, Nov 12, 2015 at 6:11 PM, Mark Carter <[email protected]> wrote:
> I am trying to implement "OrdList", which is a list that is guaranteed to
> be ordered. Here's my implementation so far:
>
> module OrdList (empty, fromList, insert, toList, OrdList(OrdList)) where
> import Data.List as L (span)
>
> data OrdList a = OrdList [a] deriving (Show)
>
>
> empty :: OrdList a
> empty = OrdList []
>
>
> insert :: (Ord a) => a -> OrdList a -> OrdList a
> insert x ol =
> let -- OrdList xs = ol
> (before, after) = L.span (\el -> el <= x) $ toList xs
> in
> OrdList $ before ++ [x] ++ after
>
> fromList :: Ord a => [a] -> OrdList a
> fromList xs =
> if null xs then empty else insert (head xs) (fromList $ tail xs)
>
> toList :: OrdList t -> [t]
> toList xs =
> let OrdList xs' = xs in xs'
>
>
>
> It "works", but no doubt there's plenty to dislike about it. Some specific
> questions I have in mind:
> 1. Should OrdList be best implemented as a class, data, or newtype? If so,
> what changes need to be made?
> 2. How comes I can't refer to OrdList as a data type? This is a problem
> because I can't say that I want the type of something to be OrdList Int,
> for example.
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20151112/b0a7c284/attachment-0001.html>
------------------------------
Message: 2
Date: Thu, 12 Nov 2015 19:57:41 +0530
From: akash g <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] question about list processing
Message-ID:
<caliga_ftikneq-j_ekxgjo32llhhuhe2xr9myvts9j8q5vv...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I think these changes came with GHC 7.10. I also completely agree that
this is difficult for beginners. They should've had a beginner's Prelude
or something :)
On Thu, Nov 12, 2015 at 7:18 PM, Dennis Raddle <[email protected]>
wrote:
> Speaking of lists and history, I noticed that a lot of library functions
> which were formerly defined over lists (when I first looked at Haskell six
> years ago) are now defined on Traversable, which makes it a lot harder for
> beginners to read the documentation. I have been playing with Haskell for
> five years, but not much, so I'm still a beginner. I just mentally
> substitute lists when I see Traversable.
>
> I only really use lists and Maybe, as far as instances of the typeclasses
> go. That's only two types, but a lot to learn!
>
> D
>
>
>
>
> On Thu, Nov 12, 2015 at 5:42 AM, akash g <[email protected]> wrote:
>
>>
>> http://stackoverflow.com/questions/7463500/why-do-we-have-map-fmap-and-liftm
>> have very good answers on this.
>>
>> On Thu, Nov 12, 2015 at 7:11 PM, akash g <[email protected]> wrote:
>>
>>> map is specialized for lists while fmap is for any functors. Its
>>> presence is historical. Prefer fmap over map.
>>>
>>> On Thu, Nov 12, 2015 at 7:03 PM, Dennis Raddle <[email protected]>
>>> wrote:
>>>
>>>> Just after I posted that question, I started driving home, and on the
>>>> drive I thought of your answer. I think I'm starting to ask the right
>>>> questions when I'm programming in Haskell. Like redundancy and bloat is a
>>>> sure sign that a more witty expression is available, and that I should
>>>> consult the typeclasses.
>>>>
>>>> Second, I am not used to the implications of laziness, so it took me a
>>>> while to hit on your solution because I keep thinking you have to map
>>>> something over the whole list, and that if you only want to map it over the
>>>> head, you are stuck.
>>>>
>>>> You can use 'map' also, instead of 'fmap', right? Is 'map' just 'fmap'
>>>> for lists?
>>>>
>>>> D
>>>>
>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> [email protected]
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>
>>>>
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20151112/f4b4550c/attachment-0001.html>
------------------------------
Message: 3
Date: Thu, 12 Nov 2015 20:01:26 +0530
From: akash g <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] question about list processing
Message-ID:
<CALiga_eux5eBcVLhR0Ch4vOkMnismFvihinpzT3EB2RhEa67=q...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
There has been discussion on the changes to the Prelude. Just found this (
https://wiki.haskell.org/Foldable_Traversable_In_Prelude).
On Thu, Nov 12, 2015 at 7:57 PM, akash g <[email protected]> wrote:
> I think these changes came with GHC 7.10. I also completely agree that
> this is difficult for beginners. They should've had a beginner's Prelude
> or something :)
>
>
>
> On Thu, Nov 12, 2015 at 7:18 PM, Dennis Raddle <[email protected]>
> wrote:
>
>> Speaking of lists and history, I noticed that a lot of library functions
>> which were formerly defined over lists (when I first looked at Haskell six
>> years ago) are now defined on Traversable, which makes it a lot harder for
>> beginners to read the documentation. I have been playing with Haskell for
>> five years, but not much, so I'm still a beginner. I just mentally
>> substitute lists when I see Traversable.
>>
>> I only really use lists and Maybe, as far as instances of the typeclasses
>> go. That's only two types, but a lot to learn!
>>
>> D
>>
>>
>>
>>
>> On Thu, Nov 12, 2015 at 5:42 AM, akash g <[email protected]> wrote:
>>
>>>
>>> http://stackoverflow.com/questions/7463500/why-do-we-have-map-fmap-and-liftm
>>> have very good answers on this.
>>>
>>> On Thu, Nov 12, 2015 at 7:11 PM, akash g <[email protected]> wrote:
>>>
>>>> map is specialized for lists while fmap is for any functors. Its
>>>> presence is historical. Prefer fmap over map.
>>>>
>>>> On Thu, Nov 12, 2015 at 7:03 PM, Dennis Raddle <[email protected]
>>>> > wrote:
>>>>
>>>>> Just after I posted that question, I started driving home, and on the
>>>>> drive I thought of your answer. I think I'm starting to ask the right
>>>>> questions when I'm programming in Haskell. Like redundancy and bloat is a
>>>>> sure sign that a more witty expression is available, and that I should
>>>>> consult the typeclasses.
>>>>>
>>>>> Second, I am not used to the implications of laziness, so it took me a
>>>>> while to hit on your solution because I keep thinking you have to map
>>>>> something over the whole list, and that if you only want to map it over
>>>>> the
>>>>> head, you are stuck.
>>>>>
>>>>> You can use 'map' also, instead of 'fmap', right? Is 'map' just 'fmap'
>>>>> for lists?
>>>>>
>>>>> D
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Beginners mailing list
>>>>> [email protected]
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>>
>>>>>
>>>>
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20151112/526e4860/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 89, Issue 19
*****************************************
