How to Implement functions from type signatures?

You have some misunderstandings there:

I understand that foo takes a function (a -> (a,b)) and returns a and a list containing b.

No, it doesn't return a. It expects it as another argument, in addition to that function.

And bar takes a function (b -> c) which returns a function (a -> b -> c) which finally returns a and c.

Same here. Given g :: a -> b, bar returns a function bar g :: (a -> b -> c) -> a -> c. This function, in turn, given a function h :: (a -> b -> c), returns a function of type a -> c. And so it goes.

It's just like playing with pieces of a puzzle:

foo :: (a -> (a,b)) -> a -> [b]
--   g   :: a -> (a,b)
--     x :: a
--   g x ::      (a,b)
foo g x = [b]  where
  (a,b) = g x

bar :: (a -> b) -> (a -> b -> c) -> a -> c
--   g   :: a -> b
--     x :: a
--   g x ::      b
--   h   :: a -> b -> c
--   h x ::      b -> c
--   h x (g x)     :: c
bar g h x = c  where
  c = ....

There's not much free choice for us here. Although, there are more ways to get more values of type b, for foo. Instead of ignoring that a in (a,b) = g x, we can use it in more applications of g, so there actually are many more possibilities there, like

foo2 :: (a -> (a,b)) -> a -> [b]
foo2 g x = [b1,b2]  where
  (a1,b1) = g x
  (a2,b2) = g a1

and many more. Still, the types guide the possible implementations. foo can even make use of foo in its implementation, according to the types:

foo3 :: (a -> (a,b)) -> a -> [b]
foo3 g x = b : bs  where
  (a,b) = g x
  bs = ...

So now, with this implementation, the previous two become its special cases: foo g x === take 1 (foo3 g x) and foo2 g x === take 2 (foo3 g x). Having the most general definition is probably best.

In addition to @will-nes's answer, it will be useful to treat (->) as a right-associative infix operator. So something like f: a -> b -> c is the same as f: a -> (b -> c). So this is saying f is a function that takes a value of type a and returns you a value of type b -> c, which is, another function, one that takes a value of type b and returns you a value of type c.

So the types in your example can be re-written as follows

foo :: (a -> (a,b)) -> (a -> [b])

bar :: (a -> b) -> ((a -> (b -> c)) -> (a -> c))

Similarly, you can think of arguments to a function in pieces as well, as being left-associative (like + and -), though there's no explicit operator in this case. foo a b c d e is the same as ((((foo a) b) c) d) e. For example, let's say we have a function f: Int -> Int -> Int (which is the same as f: Int -> (Int -> Int)). You don't have to provide both arguments at once. So you can write g = f 1, which has the type (Int -> Int). And then you can provide an argument to g, like g 2, which has the type Int. f 1 2 and let g = f 1 in g 2 are more or less the same. Here's a more concrete example of how this works:

Prelude> f = (+)
Prelude> g = f 1
Prelude> g 2
3
Prelude> :t f
f :: Num a => a -> a -> a
Prelude> :t g
g :: Num a => a -> a
Prelude> :t g 2
g 2 :: Num a => a

In @will-nes's sample implementation examples, he defines the functions with all of the arguments up front, but you don't have to think of them that way. Just think of f: a -> b -> c as taking a value of type a and returning another function. While most of the methods you encounter will use all of their arguments up-front, there might be cases in which you don't want to do that. Here's an example:

veryExpensive :: A -> B

unstagedFun :: A -> (B -> C) -> C
unstagedFun a f = f (veryExpensive a)

stagedFun :: A -> (B -> C) -> C
stagedFun a = let b = veryExpensive a in \f -> f b

(You can also rewrite the latter as let b = veryExpensive a in ($ b))

Of course, with compiler optimizations, I wouldn't be surprised if the unstaged version staged automatically, but hopefully this offers some motivation for thinking of functions as not having multiple arguments, but rather, as a single argument, but they may return other functions that may themselves return functions (but also only take a single argument).