Re: Ocaml

[Melzzzzz]

On 6 Dec 2016 23:40:45 GMT
r...@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<y then x:y:ys
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

[Marcel Mueller]

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

[Ben Bacarisse]

r...@zedat.fu-berlin.de (Stefan Ram) writes:

> 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 <algorithm>
> #include <forward_list>
> #include <iostream>
> #include <iterator> // std::ostream_iterator
> #include <ostream>
> #include <string>
>
> 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?

template<class L, class T>
void insert(L &lst, T elt)
{
lst.merge({elt});
}

?

--
Ben.

[Alain Ketterlin]

r...@zedat.fu-berlin.de (Stefan Ram) writes:

> 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:

[...]

I don't really see the point in translating this using
std::list/forward_list. More interesting would be a direct translation
using some sort of cons-list (e.g., as in
http://programminggenin.blogspot.fr/2012/10/cons-lists-in-c.html), maybe
using smart pointers.

(I've found such lists very useful on several occasions, and wonder why
the standard library doesn't include this.)

-- Alain.