-2

I am learning Haskell and now i am resolving some exercises about declaring prelude functions without importing the prelude functions which i have to resolve.

I got stuck programming the reverse function because i noticed that i can't reverse the list without (++) function. I tried using : to concatenate the lists in a reverse way but it doesn't work. Can you explain me why only the first code works and the second not? Thanks. Also I can't use pattern matching.

reverse1 :: [a] -> [a]
reverse1 = \list -> case list of {
                        [] -> [];
                        x:xs -> reverse1 xs ++ [x];
}

reverse1 :: [a] -> [a]
reverse1 = \list -> case list of {
                        [] -> [];
                        x:xs -> (reverse1 xs):(x);
}
Will Ness
  • 70,110
  • 9
  • 98
  • 181
Meto ballaes
  • 103
  • 8
  • 8
    Pattern matching is a fundamental aspect of Haskell. Forgoing the prelude is one thing (I can see the benefits of that, for learning purposes), but refusing to use pattern matching is like refusing to use if statements in Java. It can be done, but the result is [a very different programming experience](https://esolangs.org/wiki/Javagony) and *not* a good way to learn the language. Not to mention the fact that every snippet of code in your question *does* in fact use pattern matching. – Silvio Mayolo Jul 27 '21 at 04:32
  • 1
    You are using pattern matching in `case ... of`. The thing to the left of -> is a pattern. You cannot avoid it. – n. m. could be an AI Jul 27 '21 at 04:51
  • 1
    "without Prelude or pattern matching" pretty much rules out everything to access a list. Can you tell us what's allowed, exactly? I mean, `(:)` is in the prelude, so that's out, like the empty list `[]`. The type `[a]` is also in the prelude, so we can't even write the type. Without pattern matching, we can't dissect a given list except using prelude functions like `null, head, tail` but those are out (and in good code should be avoided). Folds are also in the prelude. So... what can actually be used? Surely these things can't all be out. – chi Jul 27 '21 at 08:10
  • @chi I think it's not a total prohibition on Prelude, just on the function they have to reimplement. – Will Ness Jul 27 '21 at 08:15
  • 2
    If you can use some Prelude functions and not others, please show the complete list of either allowed or forbidden functions. If you cannot use *any* Prelude functions and also cannot use pattern matching, the task is impossible. – n. m. could be an AI Jul 27 '21 at 08:16
  • @1.89e not impossible, just inconvenient. You can still write a reverse for a church encoding of a list for instance. Not likely to be what OP wants in this case of course. – Cubic Jul 27 '21 at 14:13
  • @n.1.8e9-where's-my-sharem. Ahh okay, i didn't know that i was using pattern matching. Our teacher from the university told us to only use `case of` to know exactly where it happens the recusion to then demonstrate that the functions works ∀ x – Meto ballaes Jul 27 '21 at 14:59

2 Answers2

2

There are two differences between your code snippets, and they are both important for explaining why the second one doesn't work. The first is that (++) and (:) have different types:

(++) :: [a] -> [a] -> [a]
(:)  ::  a  -> [a] -> [a]

The second is the different ways you use them:

reverse1 xs ++ [x]
reverse1 xs :   x

Now, at first glance, you might think that these two differences cancel each other out. After all, : drops a list from its type, and [x] vs. x drops a list from an argument, all good! Unfortunately, it doesn't work that way; the order of arguments matters, and the list that gets dropped in the type is on the first argument to (:), not the second. So we've gone double bad -- instead of giving (:) an thing and a more list-y thing (a and [a]), we've given it a thing and a less list-y thing ([a] and a).

In plain English: (:) adds an element to the front of a list, not the back. Bummer!

You're going to have to come up with a fundamentally different implementation approach for this to work. If you want a hint, here's a rot13'd one.

Gel vzcyrzragvat n urycre shapgvba, yrg'f fnl vg'f pnyyrq eriUryc, gung gnxrf gjb yvfgf naq ergheaf n yvfg. Gur orunivbe vg fubhyq unir vf gung eriUryc yvfgBar yvfgGjb ergheaf yvfgGjb ++ erirefr yvfgBar. Vzcyrzrag vg ivn fvzcyr cnggrea zngpuvat naq erphefvba, nf hfhny sbe yvfg shapgvbaf, ba gur yvfgGjb nethzrag. (Ab snve pnyyvat erirefr vafvqr guvf shapgvba! Vg fubhyq fgnaq nybar.) Pna lbh frr ubj gb hfr gung shapgvba gb vzcyrzrag erirefr?

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
1

The cons operator, (:), need a single element as its first argument and a List as its second. You have put a list in the head position.

Hint: In order to solve this without any prelude functions you will need to come up with your own version of foldl

John F. Miller
  • 26,961
  • 10
  • 71
  • 121