[Haskell-cafe] how to make this work recursive ?

[Roelof Wobben]

Hello,

I found out that for 1 item I can do this : node = Node leaf "msg 1" leaf
And for 2 items I can do this : node = Node leaf "msg1" (Node leaf
"msg2" leaf)

But now I wonder how I can make this work with recursion. It seems that
I keep the first 2 items and change the 3th one from leaf to another node

Roelof


_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

[Sumit Sahrawat, Maths & Computing, IIT (BHU)]

Draw the trees, and then try to partition every node into (left, element, right).

For example, in your first example (Node leaf "msg 1" leaf), we get

Node "msg 1"

├── leaf

└── leaf

In the second example,

Node "msg 1"

├── leaf

└── Node "msg 2"     -- A sub-tree

    ├── leaf

    └── leaf

Now, substituting a leaf with a Node in the above tree will lead to larger trees.

For another example, look here: http://en.wikipedia.org/wiki/Tagged_union#Examples

--

Regards

Sumit Sahrawat

[Roelof Wobben]

That part I understand .

it's more how I do it here :

Lets say I have this :

data MessageType = Info
                 | Warning
                 | Error Int
  deriving (Show, Eq)

type TimeStamp = Int

data LogMessage = LogMessage MessageType TimeStamp String
                | Unknown String
  deriving (Show, Eq)

data MessageTree = Leaf
                 | Node MessageTree LogMessage MessageTree
  deriving (Show, Eq)

Now I have to put all the LogMessages in a binary tree.
with this signature : insert :: LogMessage -> MessageTree -> MessageTree

I think I need recursion here but I still not see how I can make the clauses.
Normally you can say somethig like this  [] -> 0  or  1 ->   but here it seems to be all seperate logMessages

Roelof





Sumit Sahrawat, Maths & Computing, IIT (BHU) schreef op 28-2-2015 om 11:53:

[Sumit Sahrawat, Maths & Computing, IIT (BHU)]

First, consider the two possible cases,

insert :: LogMessage -> MessageTree -> MessageTree

insert m Leaf         = Node Leaf m Leaf     -- Inserting into an empty tree (base case for recursion)

insert m (Node l m r) = undefined            -- Try working it out here.

You will need to decide where to insert the message in a way such that the properties of binary tree are not violated.

If you can decided that at each recursive step and proceed accordingly, you will hit the base case soon enough.

[Mike Meyer]

On Sat, Feb 28, 2015 at 5:07 AM, Roelof Wobben <r.wo...@home.nl> wrote:

That part I understand .

it's more how I do it here :

Lets say I have this :

data MessageType = Info
                 | Warning
                 | Error Int
  deriving (Show, Eq)

type TimeStamp = Int

data LogMessage = LogMessage MessageType TimeStamp String
                | Unknown String
  deriving (Show, Eq)

data MessageTree = Leaf
                 | Node MessageTree LogMessage MessageTree
  deriving (Show, Eq)

Now I have to put all the LogMessages in a binary tree.
with this signature : insert :: LogMessage -> MessageTree -> MessageTree

I think I need recursion here but I still not see how I can make the clauses.
Normally you can say somethig like this  [] -> 0  or  1 ->   but here it seems to be all seperate logMessages 

Whether you need recursion or not depends on where you're to insert the message. For instance, you could turn them into a list with:

insert message tree = Node tree message Leaf

Try drawing a few pictures of what that produces, and you'll see why it's probably not what you want.

You should be able to tell by looking at the MessageTree type that you have two cases: one where you're passed something matching a Node, and one where you're passed something that's just a Leaf. The latter can't be recursive, so it's going to terminate any recursion. Following the advice given to you for the Hanoi problem, try writing it first.

Then all you have to do is figure out how to handle the case where you're given a Node instead of a Leaf.  Figuring out where in the MessageTree you want to insert the Logmessage will probably be required to do that.

[Roelof Wobben]

I tried this :

insert :: LogMessage -> MessageTree -> MessageTree

insert s =
   case words s of
       (_:_: "This is not the right format") -> MessageTree Leaf
       _                                     -> MessageTree Node LogMessage Leaf
   

But I see this errormessages which I do not understand :

src/LogAnalysis.hs@38:49-38:60

Not in scope: data constructor

MessageTree

src/LogAnalysis.hs@39:49-39:60

Not in scope: data constructor

MessageTree

Mike Meyer schreef op 28-2-2015 om 12:17:

[Sumit Sahrawat, Maths & Computing, IIT (BHU)]

You're missing an argument to insert, assuming that it is indeed there, consider this:

    insert msg tree = tree'

      where tree' = undefined

    -- Take a LogMessage (msg) and a MessageTree (tree)

    -- and return a new MessageTree (tree')

Therefore, the result of insert in your case, i.e. "MessageTree Leaf" should be of type MessageTree.
And thus, we get

    MessageTree Leaf :: MessageTree

    -- Takes a (Leaf :: LogMessage) and produces a MessageTree

which implies,

    MessageTree :: LogMessage -> MessageTree

    -- A Data constructor

Obviously no such data constructor exists. A data constructor of this type would exist only if you wrote something like:

    data MessageTree = MessageTree LogMessage

                     | ...

which would not make sense.

_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

--

Regards

Sumit Sahrawat

[Roelof Wobben]

Sorry,

But I do not understand what you mean.

What I try to do is this

If you have a LogMessage which contains " This is not the right format " then the LogMessage is not inserted in the tree.
Every other message are inserted in the tree.

So that is why I make a MessageTree with only one Leaf.

Roelof



Sumit Sahrawat, Maths & Computing, IIT (BHU) schreef op 28-2-2015 om 16:08:

[Sumit Sahrawat, Maths & Computing, IIT (BHU)]

Don't worry. Keep these points in mind and re-read my previous mail.

Regarding data vs. type constructors.

1) Leaf :: MessageTree (Leaf is a MessageTree)

2) MessageTree is a type constructor (takes types and gives new types)

3) Node is a data constructor (takes values and gives a new MessageTree)

Regarding insertion.

1) The "insert" function takes a message and tree, and returns a tree with that message inserted into it

2) We absolutely have to provide it a tree

3) If we insert an invalid message in the tree, it does not get added. Then we get ..... the same tree back.

If you still cannot see a problem in your code, ask yourself the following:

1) What type does the output of insert (MessageTree Leaf) have, and what type should it have
2) What happens if we insert an invalid string in a non-empty tree (according to your code)

Don't forget to re-read the previous mail.

Hope this drives the point home.

[Roelof Wobben]

Thanks,

Found it.

Now I have to find out how I can test if the LogMessage  has the text "this is not the right format" in it.

Roelof



Sumit Sahrawat, Maths & Computing, IIT (BHU) schreef op 28-2-2015 om 19:49:

[Roelof Wobben]

According to the manual this schould work :

-- | Parse the String to make the right logmessage
parse_line :: String -> LogMessage
parse_line s =
   case words s of
        ("I":time:text)           -> LogMessage Info (read time) (unwords text)
        ("W":time:text)           -> LogMessage Warning (read time) (unwords text)
        ("E":errorcode:time:text) -> LogMessage (Error (read errorcode)) (read time) (unwords text)
        _                         ->  Unknown "This is not in the right format"


-- | here the actual function which uses isValid and parse to make the right log messages
parseMessage :: String -> LogMessage
parseMessage s =
    if  isValid(s) then parse_line(s) else Unknown "This is not the right format"


parse :: String -> [LogMessage]
parse = (map parseMessage) . lines

insert :: LogMessage -> MessageTree -> MessageTree
insert s =

   message_text(_:text) = text ;
   case (_:text) of
       "This is not the right format" -> Leaf
       _                              -> Node LogMessage Leaf
   

but why do I set this message then :

src/LogAnalysis.hs@37:25-37:26

parse error on input

that is this line : message_text(_:text) = text

Roelof

Roelof Wobben schreef op 1-3-2015 om 11:17:

[Richard A. O'Keefe]

On 28/02/2015, at 9:40 pm, Roelof Wobben <r.wo...@home.nl> wrote:
> I found out that for 1 item I can do this : node = Node leaf "msg 1" leaf
> And for 2 items I can do this : node = Node leaf "msg1" (Node leaf "msg2" leaf)

Your subject line says "how to make THIS work recursive(ly)" but the
body of your message does not explain what "this" is.

It looks as thought you have

data BinaryTree x
= Leaf
| Node (BinaryTree x) x (BinaryTree x)

except that you have written a variable name "leaf" instead of
a constant name "Leaf" (ok, there are no constant names, it's a constructor
name, but a constructor with no arguments is a constant).

>
> But now I wonder how I can make this work with recursion.

Well, you have to START by saying clearly what "THIS" is.

It looks as though you want

empty :: BinaryTree x

insert :: Ord x => x -> BinaryTree x -> BinaryTree x

There's only one thing you can put for empty. To make a Node
you would have to a value of type t, and you don't. So

empty = Leaf

What about insert?
You have two arguments: an x (and all you know about x values is that
they can be compared) and a BinaryTree x. It's going to have to be
a case analysis on the two possibilities for the BinaryTree:

insert v Leaf = Node Leaf v Leaf
insert v (Node lss elt gtr) = ??

Where are we doing to put v? There are three places:
lss (the set of things less than elt)
elt (the value elt)
gtr (the set of things greater than elt).
How can we tell where to put v?

Answer: by comparing v with elt:

case compare v elt of
LT -> "insert v in lss"
GT -> "insert v in gtr"
EQ -> "it's already in elt"

Convert the comments to Haskell, and we have

insert v Leaf = Node Leaf v Leaf
insert v (Node lss elt gtr) =
case compare v elt of
LT -> Node (insert v lss) elt gtr
GT -> Node lss elt (insert v gtr)
EQ -> Node lss elt gtr

We don't actually *MAKE* this function work recursively,
it just *happens* that to insert an element into a big
tree, we sometimes want to insert it into a subtree.

A first or second year data structure book would do this
in C:

typedef ???? elem;

typedef struct Node *tree;
typedef struct Node {
tree lss;
elem elt;
tree gtr;
} Node;

tree insert(elem v, tree t) {
if (t == 0) { /* leaf case */
tree n = malloc(sizeof *n);
if (n == 0) abort();
n->lss = n->gtr = 0, n->elt = elt;
return n;
} else {
if (v < t->elt) {
t->lss = insert(v, t->lss);
} else
if (t->elt < v) {
t->gtr = insert(v, t->gtr);
}
return t;

}
}


> It seems that I keep the first 2 items and change the 3th one from leaf to another node

You DO NOT CHANGE ANYTHING. Given a tree and a (possibly) new element,
you construct a NEW tree which shares most of its structure with the
old one. In C, you have to destroy the old tree to make the new one.
In Haskell, you not only don't have to, you can't.

But the basic pattern:

to insert v into t
if t is empty
return a new tree just containing v
if t is not empty
if v is less than the top element of t
insert v into the left subtree of t
if v is greater than the top element of t
insert v into the right subtree of t
if v is equal to the top element of t
there is nothing to do

does not depend on which programming language you are using.

If you are alert, you will notice a strong similarity between
the structure of the DATA (a two-way choice where one choice
is simple and the other has three parts) and the structure of
the CODE (a two-way choice where one choice is simple and
the other has three parts). This is not an accident.

[Richard A. O'Keefe]

On 1/03/2015, at 2:39 am, Roelof Wobben <r.wo...@home.nl> wrote:

> I tried this :
>
> insert :: LogMessage -> MessageTree -> MessageTree
> insert s =
> case words s of
> (_:_: "This is not the right format") -> MessageTree Leaf
> _ -> MessageTree Node LogMessage Leaf

This makes no sense.
You have declared that insert takes a LogMessage argument
and a MessageTree argument and returns a MessageTree result.

Then your code DOES NOT ACCEPT A MESSAGETREE ARGUMENT!

You want to have

insert logmsg msgtree =

and the case analysis should be on the message tree, not the log message.

src/LogAnalysis.hs@38:49-38:60
> Not in scope: data constructor
> MessageTree
> src/LogAnalysis.hs@39:49-39:60
> Not in scope: data constructor
> MessageTree

The compiler is telling you, as clearly as it knows how,
that you DO NOT HAVE ANY CONSTRUCTOR FUNCTION called "MessageTree".
The constructor functions are >> Leaf << and >> Node <<.
MessageTree is a *TYPE NAME*.


I am about to be offensive.
I do not want to be offensive.
I want to be helpful.
I believe this question needs to be asked.
But there is a real risk that I will offend you.

Here goes.

Is there *any* programming language you know how to use?

The reason that I ask is that the problems you keep having
aren't really Haskell problems. They are general programming
problems:
- declaring a name as one kind of thing
and using it as if it were another
- declaring a function (like 'insert' or 'Node')
to have n arguments but trying to define or call
it with m arguments where m ~= n.
- not starting with a description of your problem
- not having a clue what to do when the compiler tells
you something. (It's OK not to understand a
compiler message. But you should get *some* clue
from it, like where exactly to look, and you should
be able to try to vary the program to see how the
message changes.)

I honestly feel that the difficulties you are reporting here
aren't really Haskell difficulties, just as the difficulties
you were reporting in the Erlang mailing list weren't really
Erlang difficulties, but in both cases, something much more
fundamental.

To restate my possibly offensive question again:

Have you ever had a course of instruction in the use of
any programming language face to face with a competent
teacher?

Again, I'm trying to be helpful here. If you run into a
problem and can get help within *minutes*, and have someone
sit down beside you at the keyboard and *show* you how to
find out what a compiler message might mean and what to do
about it, you can learn very quickly. If you have to wait
hours for responses, you are obviously going to learn much
more slowly.

I sometimes ask my students: "What's the point of coming here?
Why not just buy a textbook?" Sadly, they sometimes do not
know the answer. It's "You can ask ME questions, and each other."

It is clear that you are working at trying to learn Haskell.
It is SMART of you to ask questions.
It's just that there are these really basic issues where I
think you could learn a lot faster with face-to-face help.

[Richard A. O'Keefe]

On 1/03/2015, at 11:17 pm, Roelof Wobben <r.wo...@home.nl> wrote:
>
> Now I have to find out how I can test if the LogMessage has the text "this is not the right format" in it.

Well, the Haskell libraries include regular expression support.
At an elementary level, you can always do

is_prefix_of :: Eq x => [x] -> [x] -> Bool
is_prefix_of (x:xs) (y:ys) = x == y && is_prefix_of xs ys
is_prefix_of (x:xs) [] = False
is_prefix_of [] _ = True


is_infix_of :: Eq x => [x] -> [x] -> Bool

is_infix_of xs ys =
xs `is_prefix_of` ys || (not (null ys) && xs `is_infix_of` tail ys)


"this is not the right format" `is_infix_of` aLogMessage

But it would be better if your LogMessage were not a string
but something structured where you did not have to go looking
for that text because you KNEW where to look for it.

[Roelof Wobben]

Richard A. O'Keefe schreef op 2-3-2015 om 0:31:

Thanks for the explanation.

Roelof

[Roelof Wobben]

Richard A. O'Keefe schreef op 2-3-2015 om 0:49:

I have not done any face to face courses.
Programming is a hobby for me.

Roelof

[Roelof Wobben]

Richard A. O'Keefe schreef op 2-3-2015 om 0:59:

> On 1/03/2015, at 11:17 pm, Roelof Wobben <r.wo...@home.nl> wrote:
>> Now I have to find out how I can test if the LogMessage has the text "this is not the right format" in it.
>
> Well, the Haskell libraries include regular expression support.
> At an elementary level, you can always do
>
> is_prefix_of :: Eq x => [x] -> [x] -> Bool
> is_prefix_of (x:xs) (y:ys) = x == y && is_prefix_of xs ys
> is_prefix_of (x:xs) [] = False
> is_prefix_of [] _ = True
>
>
> is_infix_of :: Eq x => [x] -> [x] -> Bool
>
> is_infix_of xs ys =
> xs `is_prefix_of` ys || (not (null ys) && xs `is_infix_of` tail ys)
>
>
> "this is not the right format" `is_infix_of` aLogMessage
>
> But it would be better if your LogMessage were not a string
> but something structured where you did not have to go looking
> for that text because you KNEW where to look for it.
>
>

I know where to look.

A LogMessage looks like this :

data LogMessage = LogMessage MessageType TimeStamp String
| Unknown String
deriving (Show, Eq)

So if it's Unknown with a string then it will not be inserted into the
MessageTree
The only thing I have to find out if LogMessage contains this.

Roelof

[o...@cs.otago.ac.nz]

You are still not being clear.
You have

data LogMessage
= LogMessage MessageType TimeStamp String
| Unknown String
deriving (Show, Eq)

> So if it's Unknown with a string then it will not be inserted into the
> MessageTree
> The only thing I have to find out if LogMessage contains this.

Question 1.
Your description seems contradictory.
The first sentence is talking about the Unknown case.
The second sentence appears to be talking about the other
case.
Do you mean

should_discard (LogMessage _ _ _) = False
should_discard (Unknown s) = ...s contains magic...

or

should_discard (LogMessage _ _ s) = ...s contains magic...
should_discard (Unknown _) = False

or

should_discard (LogMessage Error _ s) = ...s contains magic...
should_discard _ = False

or what?

Question 2.

What do you mean by "contains"?
Do you mean
- is exactly equal to
- is equal to ignoring leading and trailing white space
and treating runs of white space as single spaces
- is equal to ignoring alphabetic case
- equality up to some other predicate
- contains a substring equal to
(this is what I first thought you meant)
- contains a substring equivalent to up to some predicate
or something else?

In short, before you can ask how to do "this",
you have to say in plain words what "this" IS.

The _answer_ will be concerned with Haskell,
but _the way you should ask such questions_ is not.

In any programming language, whatever code you write is going to
have *some* precise meaning. The industry as a whole has a huge
problem with differences between what people *want* their
program to mean/do and what it *does* mean/do. We haven't a hope
of detecting such problems in good time if we aren't clear about
what it is that we want.

Here's another tip. Some people find it helps.

Before you start to write a function, just write a stub (others
have shown you examples, using 'undefined' as the body; that's
a stub), and write test cases that call it. This may help to
clarify your ideas about what you want the function to do with
_those_ examples, and thereby about others.