MESSAGE
| DATE | 2016-12-06 |
| FROM | ruben safir
|
| SUBJECT | Subject: [Learn] Fwd: Ocaml
|
From learn-bounces-at-nylxs.com Tue Dec 6 20:54:57 2016
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id 3F601161312;
Tue, 6 Dec 2016 20:54:57 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62])
by mrbrklyn.com (Postfix) with ESMTP id 233DC160E77
for ; Tue, 6 Dec 2016 20:54:35 -0500 (EST)
References:
<20161207010812.7955a077-at-maxa-pc>
To: learn-at-nylxs.com
From: ruben safir
X-Forwarded-Message-Id:
<20161207010812.7955a077-at-maxa-pc>
Message-ID: <85831a12-aa4c-446d-5a26-2c4e013db51f-at-mrbrklyn.com>
Date: Tue, 6 Dec 2016 20:54:35 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
MIME-Version: 1.0
In-Reply-To:
Content-Type: multipart/mixed; boundary="------------1EA036717130F8256DEF122E"
Subject: [Learn] Fwd: Ocaml
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
This is a multi-part message in MIME format.
--------------1EA036717130F8256DEF122E
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
--------------1EA036717130F8256DEF122E
Content-Type: message/rfc822;
name="Ocaml.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Ocaml.eml"
Path: reader1.panix.com!panix!goblin3!goblin.stu.neva.ru!news-1.dfn.de!news.dfn.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: ram-at-zedat.fu-berlin.de (Stefan Ram)
Newsgroups: comp.lang.c++
Subject: Ocaml
Date: 6 Dec 2016 23:40:45 GMT
Organization: Stefan Ram
Expires: 1 Jan 2017 11:59:58 GMT
Message-ID:
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: news.uni-berlin.de /DH0NvXrik0nb/35wj4+IAWZ8Ne11c43APCOzStuIwF8li
X-Copyright: (C) Copyright 2016 Stefan Ram. All rights reserved.
Distribution through any means other than regular usenet
channels is forbidden. It is forbidden to publish this
article in the world wide web. It is forbidden to change
URIs of this article into links. It is forbidden to remove
this notice or to transfer the body without this notice.
X-No-Archive: Yes
Archive: no
X-No-Archive-Readme: "X-No-Archive" is only set, because this prevents some
services to mirror the article via the web (HTTP). But Stefan Ram
hereby allows to keep this article within a Usenet archive server
with only NNTP access without any time limitation.
X-No-Html: yes
Content-Language: en
Xref: panix comp.lang.c++:1125877
Today, I read a bit in an Ocaml manual which said
insert elt lst =
match lst with
[] -> [elt]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
as a part of an insertation-sort program.
I was trying to translate that into C++, and got this:
main.cpp
#include
#include
#include
#include // std::ostream_iterator
#include
#include
using namespace ::std::literals;
template< class L, class I, class T >
void insert( L & lst, I bbegin, I begin, I end, T elt )
{ if( begin == end )lst.insert_after( bbegin, elt ); else
{ if( elt <= lst.front() )lst.insert_after( bbegin, elt ); else
insert( lst, ++bbegin, ++begin, end, elt ); }}
int main()
{ ::std::forward_list< int >list;
::insert( list, list.before_begin(), list.begin(), list.end(), 50 );
::insert( list, list.before_begin(), list.begin(), list.end(), 30 );
::insert( list, list.before_begin(), list.begin(), list.end(), 70 );
copy( list.begin(), list.end(), ::std::ostream_iterator< int >( ::std::cout, " " ));
::std::cout << '\n'; }
transcript
30 50 70
Can my C++ ::insert function be simplified?
--------------1EA036717130F8256DEF122E
Content-Type: message/rfc822;
name="Re: Ocaml.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Ocaml.eml"
Path: reader1.panix.com!panix!goblin2!goblin1!goblin.stu.neva.ru!news.albasani.net!.POSTED!not-for-mail
From: Melzzzzz
Newsgroups: comp.lang.c++
Subject: Re: Ocaml
Date: Wed, 7 Dec 2016 01:08:12 +0100
Organization: albasani.net
Message-ID: <20161207010812.7955a077-at-maxa-pc>
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-Trace: news.albasani.net RxmFL9CijITKVlGzMRu3XMmQVMNGc0UtpFtQbSvlqQ+7qfTuWJO42ZNBrAfUOGN8odXrbpghxCSQtxOHw/+sfA==
NNTP-Posting-Date: Wed, 7 Dec 2016 00:08:12 +0000 (UTC)
Injection-Info: news.albasani.net; logging-data="gI4dItmP2MaQe0uF/MconBwETn0LAD2L6bf8ipImYWMmZCRmny8im7hmZ5ImnGCASxOdk1PKLh+RCyBm++EsqhY7jq8ny7CY3aQgA4r8Dzkc2A+zBT3o0bVCcJ3QsR2M"; mail-complaints-to="abuse-at-albasani.net"
X-Newsreader: Claws Mail 3.14.1 (GTK+ 2.24.31; x86_64-unknown-linux-gnu)
Cancel-Lock: sha1:67LihbZ21PxKbkADOcZxIIyNXs0=
Xref: panix comp.lang.c++:1125878
On 6 Dec 2016 23:40:45 GMT
ram-at-zedat.fu-berlin.de (Stefan Ram) wrote:
> Today, I read a bit in an Ocaml manual which said
>
> insert elt lst =
> match lst with
> [] -> [elt]
> | head :: tail -> if elt <= head then elt :: lst else head :: insert
> elt tail
>
> as a part of an insertation-sort program.
>
>
> Can my C++ ::insert function be simplified?
Functional languages have great expressive power when working with
lists.
>
Haskell:
isort :: Ord a => [a] -> [a]
isort xs = foldr insert [] xs
where
insert x [] = [x]
insert x (y:ys) = if x else y: insert x ys
msort :: Ord a =>[a] -> [a]
msort xs
| n < 2 = xs
| otherwise = merge (msort x1s) (msort x2s)
where
n = length xs
(x1s,x2s) = splitAt (n`quot`2) xs
merge xs ys = case (xs,ys) of
([], ys') -> ys'
(xs', []) -> xs'
(x:xs',y:ys') | x < y -> x : merge xs' ys
| otherwise -> y : merge xs ys'
--
press any key to continue or any other to quit
--------------1EA036717130F8256DEF122E
Content-Type: message/rfc822;
name="Re: Ocaml.eml"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment;
filename="Re: Ocaml.eml"
Path: reader1.panix.com!panix!goblin2!goblin1!goblin.stu.neva.ru!fu-berlin.de!uni-berlin.de!not-for-mail
From: ram-at-zedat.fu-berlin.de (Stefan Ram)
Newsgroups: comp.lang.c++
Subject: Re: Ocaml
Date: 7 Dec 2016 00:13:32 GMT
Organization: Stefan Ram
Expires: 1 Jan 2017 11:59:58 GMT
Message-ID:
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: news.uni-berlin.de rz39KSRxShCIcVawPU87vQ7s7Q2556mvwJ5nkHFAhxj7Cx
X-Copyright: (C) Copyright 2016 Stefan Ram. All rights reserved.
Distribution through any means other than regular usenet
channels is forbidden. It is forbidden to publish this
article in the world wide web. It is forbidden to change
URIs of this article into links. It is forbidden to remove
this notice or to transfer the body without this notice.
X-No-Archive: Yes
Archive: no
X-No-Archive-Readme: "X-No-Archive" is only set, because this prevents some
services to mirror the article via the web (HTTP). But Stefan Ram
hereby allows to keep this article within a Usenet archive server
with only NNTP access without any time limitation.
X-No-Html: yes
Content-Language: en
Xref: panix comp.lang.c++:1125879
ram-at-zedat.fu-berlin.de (Stefan Ram) writes:
>{ if( begin == end )lst.insert_after( bbegin, elt ); else
> { if( elt <= lst.front() )lst.insert_after( bbegin, elt ); else
PS: I think the comparison should be ?elt <= *begin?.
--------------1EA036717130F8256DEF122E
Content-Type: message/rfc822;
name="Re: Ocaml.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: Ocaml.eml"
Path: reader1.panix.com!panix!goblin3!goblin.stu.neva.ru!news.mb-net.net!open-news-network.org!.POSTED!not-for-mail
From: Marcel Mueller
Newsgroups: comp.lang.c++
Subject: Re: Ocaml
Date: Wed, 07 Dec 2016 01:23:05 +0100
Organization: MB-NET.NET for Open-News-Network e.V.
Message-ID:
References:
NNTP-Posting-Host: aftr-95-222-30-20.unity-media.net
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: gwaiyur.mb-net.net 1481070185 19796 95.222.30.20 (7 Dec 2016 00:23:05 GMT)
X-Complaints-To: abuse-at-open-news-network.org
NNTP-Posting-Date: Wed, 7 Dec 2016 00:23:05 +0000 (UTC)
User-Agent: Mozilla/5.0 (OS/2; Warp 4.5; rv:24.0) Gecko/20100101 Thunderbird/24.8.1
In-Reply-To:
Xref: panix comp.lang.c++:1125880
On 07.12.16 00.40, Stefan Ram wrote:
> Today, I read a bit in an Ocaml manual which said
>
> insert elt lst =
> match lst with
> [] -> [elt]
> | head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
>
> as a part of an insertation-sort program.
>
> I was trying to translate that into C++, and got this:
>
> template< class L, class I, class T >
> void insert( L & lst, I bbegin, I begin, I end, T elt )
> { if( begin == end )lst.insert_after( bbegin, elt ); else
> { if( elt <= lst.front() )lst.insert_after( bbegin, elt ); else
> insert( lst, ++bbegin, ++begin, end, elt ); }}
This is buggy as lst.front() will not take care of the incremented begin
iterator on recursive calls. It just happens to work for your test case.
> Can my C++ ::insert function be simplified?
Well, in C++ probably nobody would write this as a recursion.
But, of course, this could be done.
At least you could eliminate the parameters begin and end and the
duplicate insert_after.
void insert(L& lst, I bbegin, T elt)
{ I old_begin = bbegin++;
if (bbegin == lst.end() || elt <= *bbegin)
lst.insert_after(old_bbegin, elt);
else
insert(lst, bbegin, elt);
}
But as already mentioned, a simple while loop would do the job even
better and eliminates the bbegin parameter too.
OK, if the compiler can handle TCO the generated code might be almost
the same and not recursive in both cases. But it cannot eliminate the
additional bbegin parameter at the initial call from main unless
everything is inlined.
Marcel
--------------1EA036717130F8256DEF122E
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
--------------1EA036717130F8256DEF122E--
|
|
